Minnesota Journal of Undergraduate Mathematics

Statistics on Almost-Fibonacci Pattern-Avoiding Permutations

Brody John Lynch

Carleton College

Yihan Qin

Carleton College

---

Abstract

We prove that |Avn(231, 312, 4321, 21543)|, |Av_n(321, 231, 4123, 21534)|, |Av_n(231, 312, 1432)|, and

|Av_n(312, 321, 1342)| are all equal to F_n+1-1 where F_n is the n-th Fibonacci number using the convention

F₀ = F₁ = 1 and Av_n(σ₁, …, σ_k) is the set of all permutations of length n that avoid all of the patterns

σ₁ through σ_k. To do this, we first characterize the structures of the permutations in these sets in terms

of Fibonacci permutations. Then, we further quantify the structures using statistics such as inversion

number and a statistic that measures the length of Fibonacci subsequences. Finally, we encode these

statistics in generating functions written in terms of the generating function for Fibonacci permutations.

We use these generating functions to find analogs of Fibonacci identities including the recurrence relation

and an addition formula.