### Abstract

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.

Language | English |
---|---|

Article number | R39 |

Number of pages | 18 |

Journal | The Electronic Journal of Combinatorics |

Volume | 12 |

Publication status | Published - 17 Aug 2005 |

### Fingerprint

### Keywords

- bicoloured Dyck path
- Dyck path
- segmented permutations

### Cite this

*The Electronic Journal of Combinatorics*,

*12*, [R39].

}

*The Electronic Journal of Combinatorics*, vol. 12, R39.

**Counting segmented permutations using bicoloured Dyck paths.** / Claesson, Anders.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Counting segmented permutations using bicoloured Dyck paths

AU - Claesson, Anders

PY - 2005/8/17

Y1 - 2005/8/17

N2 - 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 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.

AB - 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 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.

KW - bicoloured Dyck path

KW - Dyck path

KW - segmented permutations

UR - http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r39

M3 - Article

VL - 12

JO - The Electronic Journal of Combinatorics

T2 - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1077-8926

M1 - R39

ER -