To flatten a permutation expressed as a product of disjoint cycles, we mean to form another permutation by erasing the parentheses which enclose the cycles of the original. This clearly depends on how the cycles are listed. For permutations written in the standard cycle form-cycles arranged in increasing order of their first entries, with the smallest element first in each cycle-we count the permutations of (n) whose flattening avoids any subset of S3. Among the sequences that arise are central binomial coefficients, Schroder numbers, and relatives of the Fibonacci numbers. In some instances, we provide combinatorial arguments of the result, while in others, our approach is more algebraic. In a couple of the cases, we define an explicit bijection between the subset of Sn in question and a restricted set of lattice paths. In another, to establish the result, we make use of the kernel method to solve a functional equation arising once a certain parameter has been considered.
|Pure Mathematics and Applications
|פורסם - 1 ינו׳ 2011