Enumeration of non-crossing pairings on bit strings

Details Enumeration of non-crossing pairings on bit strings Enumeration of non-crossing pairings on bit strings

2009-06-11

arxiv.org/abs/0906.2183v2

Mathematics

Combinatorics

27 pages, 14 figures

Scientific paper

A non-crossing pairing on a bitstring matches 1s and 0s in a manner such that the pairing diagram is nonintersecting. By considering such pairings on arbitrary bitstrings $1^{n_1} 0^{m_1} ... 1^{n_r} 0^{m_r}$, we generalize classical problems from the theory of Catalan structures. In particular, it is very difficult to find useful explicit formulas for the enumeration function $\phi(n_1, m_1, ..., n_r, m_r)$, which counts the number of pairings as a function of the underlying bitstring. We determine explicit formulas for $\phi$, and also prove general upper bounds in terms of Fuss-Catalan numbers by relating non-crossing pairings to other generalized Catalan structures (that are in some sense more natural). This enumeration problem arises in the theory of random matrices and free probability.

Affiliated with

Also associated with

No associations

Rating

Enumeration of non-crossing pairings on bit strings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Enumeration of non-crossing pairings on bit strings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enumeration of non-crossing pairings on bit strings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-517004