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)|, |Avn(321, 231, 4123, 21534)|, |Avn(231, 312, 1432)|, and

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

F0 = F1 = 1 and Avn1, …, σk) is the set of all permutations of length n that avoid all of the patterns

σ1 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.