Enumeration of non-crossing pairings on bit strings

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:118

Article

Kemp, Todd¹  Mahlburg, Karl²  Rattan, Amarpreet³  Smyth, Clifford⁴ 

[1] UCSD, Dept Math, La Jolla, CA 92093 USA

[2] Princeton Univ, Dept Math, Princeton, NJ 08540 USA

[3] Univ Bristol, Dept Math, Bristol BS8 1TW, Avon, England

[4] Univ N Carolina, Dept Math & Stat, Greensboro, NC 27402 USA

关键词: Non-crossing pairings;    Free probability and random matrices;    Fuss-Catalan numbers;    Bijective combinatorics;   

DOI  :  10.1016/j.jcta.2010.07.002

来源: Elsevier

【 摘 要 】

A non-crossing pairing on a bit string is a matching of Is and Os in the string with the property that the pairing diagram has no crossings For an arbitrary bit-string w = 1(p1)O(q1) 1(pr)O(qr) let phi(w) be the number of such pairings This enumeration problem arises when calculating moments in the theory of random matrices and free probability and we are interested in determining useful formulas and asymptotic estimates for phi(w) Our main results include explicit formulas in the symmetric case where each p(i)=q(i) as well as upper and lower bounds for phi(w) that are uniform across all words of fixed length and fixed r In addition we offer more refined conjectural expressions for the upper bounds Our proofs follow from the construction of combinatorial mappings from the set of non-crossing pairings into certain generalized Catalan structures that include labeled trees and lattice paths (C) 2010 Elsevier Inc All rights reserved

【 授权许可】

Free