# Counting segmented permutations using bicoloured Dyck paths

Claesson, Anders
(2005)
*Counting segmented permutations using bicoloured Dyck paths.*
The Electronic Journal of Combinatorics, 12.
R39.
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.

#### ORCID iDs

Claesson, Anders ORCID: https://orcid.org/0000-0001-5797-8673;Item type: Article ID code: 49794 Dates: DateEvent17 August 2005PublishedKeywords: 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: 01 Jan 2021 05:17 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/49794