\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
\nopagenumbers
\noindent
%
%
{\bf Anders Claesson }
%
%
\medskip
\noindent
%
%
{\bf Counting Segmented Permutations Using Bicoloured Dyck Paths}
%
%
\vskip 5mm
\noindent
%
%
%
%
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 $\pi$ is {\it$\sigma$-segmented} if every occurrence
$o$ of $\sigma$ in $\pi$ is a segment-occurrence (i.e., $o$ is a
contiguous subword in $\pi$).
  
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.

\bye

.