  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.
