Forbidden subwords in permutations

Sergi Elizalde Marc Noy

To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-26, 2001


Let $m\le n$ be two positive integers. We say that a permutation $\pi\in\S_n$ \emph{contains} a permutation $\sigma\in\S_m$ \emph{as a subword} if there exist $m$ \emph{consecutive} elements $\pi_{l+1},\ldots,\pi_{l+m}$ such that $\reduction(\pi_{l+1},\ldots,\pi_{l+m})=\sigma$, where $\reduction$ is the reduction consisting in relabeling the elements with $\{1,\ldots,m\}$ keeping the same order relationships they had in $\pi$. In this paper we study the distribution of the number of occurrences of $\sigma$ as a subword among all permutations in ${\cal S}_n$. We solve the problem in several cases depending on the shape of $\sigma$ by obtaining the corresponding bivariate exponential generating functions as solutions of certain linear differential equations with polynomial coefficients.

Server START Conference Manager
Update Time 23 Feb 2001 at 08:48:03
Start Conference Manager
Conference Systems