2002/03/21 by Eric S. Egge, Egge, Eric S., Toufik Mansour +1
Mathematics · Physics and Astronomy · #05A15 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Advanced Mathematical Theories and Applications #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A15
paper · pdf · doi:10.48550/arxiv.math/0203226
29 pages
arxiv created 2002/03/21 · openalex publication_date 2002/03/21 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A permutation π∈ Sn is said to \it avoid a permutation σ∈ Sk whenever π contains no subsequence with all of the same pairwise comparisons as σ. For any set R of permutations, we write Sn(R) to denote the set of permutations in Sn which avoid every permutation in R. In 1985 Simion and Schmidt showed that |Sn(132, 213, 123)| is equal to the Fibonacci number Fn+1. In this paper we generalize this result in several ways. We first use a result of Mansour to show that for any permutation τ in a certain infinite family of permutations, |Sn(132, 213, τ)| is given in terms of Fibonacci numbers or k-generalized Fibonacci numbers. In many cases we give explicit enumerations, which we prove bijectively. We then use generating function techniques to show that for any permutation γ in a second infinite family of permutations, |Sn(123, 132, γ)| is also given in terms of Fibonacci numbers or k-generalized Fibonacci numbers. In many cases we give explicit enumerations, some of which we prove bijectively. We go on to use generating function techniques to show that for any permutation ω in a third infinite family of permutations, |Sn(132, 2341, ω)| is given in terms of Fibonacci numbers, and for any permutation μ in a fourth infinite family of permutations, |Sn(132, 3241, μ)| is given in terms of Fibonacci numbers and k-generalized Fibonacci numbers. In several cases we give explicit enumerations. We conclude by giving an infinite class of examples of a set R of permutations for which |Sn(R)| satisfies a linear homogeneous recurrence relation with constant coefficients.