# Counting segmented permutations using bicoloured Dyck paths

Claesson, Anders
(2005)
*Counting segmented permutations using bicoloured Dyck paths.*
The Electronic Journal of Combinatorics, 12.
ISSN 1077-8926

## 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 π 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.

Item type: | Article |
---|---|

ID code: | 49794 |

Keywords: | bicoloured Dyck path, Dyck path, segmented permutations, Electronic computers. Computer science, Computational Theory and Mathematics, Geometry and Topology, Theoretical Computer Science |

Subjects: | Science > Mathematics > Electronic computers. Computer science |

Department: | Faculty of Science > Computer and Information Sciences |

Depositing user: | Pure Administrator |

Date deposited: | 14 Oct 2014 13:49 |

Last modified: | 07 Jan 2017 04:18 |

Related URLs: | |

URI: | https://strathprints.strath.ac.uk/id/eprint/49794 |

Export data: |