On the Enumeration of Non-Crossing Pairings of Well-Balanced Binary Strings Academic Article uri icon

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.

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