Counting segmented permutations using bicoloured Dyck paths (Q2571282)

For two permutations, \(\pi\in S_n\) and \(\sigma\in S_k\) with \(k\leq n\), an occurence of pattern \(\sigma\) in \(\pi\) is a subword of length \(k\) in \(\pi\) that exhibits the same relative order of its elements as \(\sigma\) does. A permutation \(\pi\) is called \(\sigma\)-segmented, if all realizations of the pattern \(\sigma\) in \(\pi\) happen on segments, i.e. on some \(k\) consecutive entries. A bicoloured Dyck path is a Dyck path, in which every up-step is assigned one of two colors, say red and green. The paper establishes one-to-one correspondence between 132-segmented permutations of length \(n\) with \(k\) occurences of 132 and bicoloured Dyck paths of length \(2n-4k\) with \(k\) red up-steps; and between 123-segmented permutations of length \(n\) with \(k\) occurences of 123 and bicoloured Dyck paths of length \(2n-4k\) with \(k\) red up-steps, each of height less than 2. Finally, a bivariate generating function is given for 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.