Restricted Permutations, Fibonacci Numbers, and k-generalized Fibonacci Numbers
| dc.creator | Egge, Eric S. | |
| dc.creator | Mansour, Toufik | |
| dc.date | 2002-03-21 | |
| dc.date.accessioned | 2026-07-07T04:47:13Z | |
| dc.date.available | 2026-07-07T04:47:13Z | |
| dc.description | A permutation $π\in S_n$ is said to {\it avoid} a permutation $σ\in S_k$ whenever $π$ contains no subsequence with all of the same pairwise comparisons as $σ$. For any set $R$ of permutations, we write $S_n(R)$ to denote the set of permutations in $S_n$ which avoid every permutation in $R$. In 1985 Simion and Schmidt showed that $|S_n(132, 213, 123)|$ is equal to the Fibonacci number $F_{n+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, $|S_n(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, $|S_n(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, $|S_n(132, 2341, ω)|$ is given in terms of Fibonacci numbers, and for any permutation $μ$ in a fourth infinite family of permutations, $|S_n(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 $|S_n(R)|$ satisfies a linear homogeneous recurrence relation with constant coefficients. | |
| dc.description | 29 pages | |
| dc.identifier | https://arxiv.org/abs/math/0203226 | |
| dc.identifier | http://arxiv.org/abs/math/0203226 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/63628 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A15 | |
| dc.title | Restricted Permutations, Fibonacci Numbers, and k-generalized Fibonacci Numbers | |
| dc.type | text |