Counting segmented permutations using bicoloured Dyck paths

Rannsóknarafurð: Framlag til fræðitímaritsGreinritrýni

Útdráttur

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 π is σ-segmented if every occurrence o of σ in π is a segment-occurrence (i.e., o is a contiguous subword in π). We show combinatorially the following 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 In - 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.

Upprunalegt tungumálEnska
FræðitímaritElectronic Journal of Combinatorics
Bindi12
Númer tölublaðs1 R
DOI
ÚtgáfustaðaÚtgefið - 17 ágú. 2005

Fingerprint

Sökktu þér í rannsóknarefni „Counting segmented permutations using bicoloured Dyck paths“. Saman myndar þetta einstakt fingrafar.

Vitna í þetta