## Ú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ál | Enska |
---|---|

Fræðitímarit | Electronic Journal of Combinatorics |

Bindi | 12 |

Númer tölublaðs | 1 R |

DOI | |

Útgáfustaða | Útgefið - 17 ágú. 2005 |