Constraint-sensitive Catalan path statistics having the Narayana distribution (Q1300988)

This paper investigates certain statistics on the set \(C(n)\) of Catalan paths, represented as length \(2n\) sequences of 0s and 1s, corresponding to vertical and horizontal steps respectively. The statistics of interest all have the Narayana distribution; that is, if \(\Theta\) is such a statistic, then \[ \#\{P\in C(n):\Theta(P)= k\}= {1\over n} {n\choose k}{n\choose k+1}. \] Moreover, the statistics studied measure certain path behaviors near the constraining line \(y= x\). The main result is a matrix encoding scheme which gives all (50) Narayana distributed statistics satisfying the author's ``constraint even-odd-even-odd'' condition. Each of the statistics is related (sometimes bijectively) to one of four ``parent'' statistics, each of which records a particular type of behavior near the constraint. The proof uses a straightforward computer program to produce candidates. Verification is accomplished using bijections and generating function techniques.