Counting Segmented Permutations Using Bicoloured Dyck Paths

Abstract

A bicoloured Dyck path is a Dyck path in which each up-step is assigned one of two colours, say, red and green. We say that a permutation $\pi$ is $\sigma$-segmented if every occurrence $o$ of $\sigma$ in $\pi$ is a segment-occurrence (i.e., $o$ is a contiguous subword in $\pi$).

We show combinatorially the following two results: The $132$-segmented permutations of length $n$ with $k$ occurrences of $132$ are in one-to-one correspondence with bicoloured Dyck paths of length $2n-4k$ with $k$ red up-steps. Similarly, the $123$-segmented permutations of length $n$ with $k$ occurrences of $123$ are in one-to-one correspondence with bicoloured Dyck paths of length $2n-4k$ with $k$ red up-steps, each of height less than $2$.

We enumerate the permutations above by enumerating the corresponding bicoloured Dyck paths. More generally, we present a bivariate generating function for the number of bicoloured Dyck paths of length $2n$ with $k$ red up-steps, each of height less than $h$. This generating function is expressed in terms of Chebyshev polynomials of the second kind.