Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Fixed Avoiders of the Third Iterate

Abstract

The generating functions for 231- and 312-avoiders fixed by the third iterate of the fundamental bijection are rational.

Theorem 1.1 (The third-iterate generating function).

Lean statement: D5/S3/Combinatorics/FundamentalBijection/ThetaCube.result

Proof. Machine-checked in Lean as D5/S3/Combinatorics/FundamentalBijection/ThetaCube.result (✓ std3). ∎

Resolves. Problems/archer-laudone-theta-cube-231-312 (proved) by D5/S3/Combinatorics/FundamentalBijection/ThetaCube.result.

Source. Repository-derived.

Acknowledgement. Kassie Archer, Robert P. Laudone (2024). Pattern avoidance and the fundamental bijection. DOI: 10.48550/arXiv.2407.06338. URL: https://arxiv.org/abs/2407.06338v1.

Commentary.

For each pattern sigma equal to 231 or 312, the ordinary generating function for sigma-avoiding permutations fixed by the third iterate of the fundamental bijection, multiplied by 1 - x - x squared - 2x cubed, equals one.

References