On the Enumeration of Non-Crossing Pairings of Well-Balanced Binary Strings

abstract

• A non-crossing pairing on a binary string pairs ones and zeroes such that the arcs representing the pairings are non-crossing. A binary string is well-balanced if it is of the form 1a10a11a20a2 . . .1ar0ar. In this paper we establish connections between non-crossing pairings of well-balanced binary strings and various lattice paths in plane. We show that for well-balanced binary strings with a1a2 . . . ar, the number of non-crossing pairings is equal to the number of lattice paths on the plane with certain right boundary, and hence can be enumerated by differential Goncarov polynomials. For the regular binary strings S = (1k0k)n, the number of non-crossing pairings is given by the (k + 1)-Catalan numbers. We present a simple bijective proof for this case. 2013 Springer Basel.

authors

• Yan, Catherine

published proceedings

• ANNALS OF COMBINATORICS

author list (cited authors)

• Schumacher, P., & Yan, C. H.

citation count

• 1

complete list of authors

• Schumacher, Paul RF||Yan, Catherine H

publication date

• June 2013

publisher

• Springer Nature  Publisher

published in

• Annals of Combinatorics  Journal

keywords

• Binary Strings
• Noncrossing

Digital Object Identifier (DOI)

• 10.1007/s00026-013-0186-5

start page

• 379

end page

• 391

volume

• 17

issue

• 2

URL

• http://dx.doi.org/10.1007/s00026-013-0186-5