Bicoloured Dyck paths and the contact polynomial for \(n\) non-intersecting paths in a half-plane lattice

R. Brak ; J. W. Essam

The electronic journal of combinatorics, Tome 10 (2003)

Résumé

In this paper configurations of $n$ non-intersecting lattice paths which begin and end on the line $y=0$ and are excluded from the region below this line are considered. Such configurations are called Hankel $n-$paths and their contact polynomial is defined by $\hat{Z}^{\cal{H}}_{2r}(n;\kappa)\equiv \sum_{c= 1}^{r+1} |{\cal H}_{2r}^{(n)}(c)|\kappa^c$ where ${\cal H}_{2r}^{(n)}(c)$ is the set of Hankel $n$-paths which make $c$ intersections with the line $y=0$ the lowest of which has length $2r$. These configurations may also be described as parallel Dyck paths. It is found that replacing $\kappa$ by the length generating function for Dyck paths, $\kappa(\omega) \equiv \sum_{r=0}^\infty C_r \omega^r$, where $C_r$ is the $r^{th}$ Catalan number, results in a remarkable simplification of the coefficients of the contact polynomial. In particular it is shown that the polynomial for configurations of a single Dyck path has the expansion $\hat{Z}^{\cal{H}}_{2r}(1;\kappa(\omega)) = \sum_{b=0}^\infty C_{r+b}\omega^b$. This result is derived using a bijection between bi-coloured Dyck paths and plain Dyck paths. A bi-coloured Dyck path is a Dyck path in which each edge is coloured either red or blue with the constraint that the colour can only change at a contact with the line $y=0$. For $n>1$, the coefficient of $\omega^b$ in $\hat{Z}^{\cal{W}}_{2r}(n;\kappa(\omega))$ is expressed as a determinant of Catalan numbers which has a combinatorial interpretation in terms of a modified class of $n$ non-intersecting Dyck paths. The determinant satisfies a recurrence relation which leads to the proof of a product form for the coefficients in the $\omega$ expansion of the contact polynomial.

Détail

DOI : 10.37236/1728

Classification : 05A15
Mots-clés : Hankel \(n\)-path, configurations, generating function