The Distribution of Double Deficiencies in Pattern-Avoiding Permutations
Abstract
We study the distribution of the number of double deficiencies (DD) in permutations of length n avoiding one or two patterns of length 3. Using structural decompositions of these avoidance classes--together with a lattice-path decomposition in the 321-avoiding case--we derive functional equations and convolution-type recurrences that efficiently compute the corresponding double-deficiency generating functions in all but one single-pattern case. In the 321-avoiding permutations, the resulting generating function is algebraic; we derive exact formulas for the mean and variance and prove that the distribution is close in total variation to Bin(n-2,1/4), with an explicit convergence rate. We also identify a DD-preserving symmetry that yields DD-Wilf equivalences, reducing the number of two-pattern cases that need to be considered separately. For the resulting two-pattern classes, we obtain explicit recurrences, including C-finite relations.
Related
- Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231
- Inversion-descent enumerators of underline321-avoiding permutations
- Avoiding patterns with three distinct letters in Canon permutations
- Descent Tops and Pinnacles on 2143- and 3421-Avoiding Permutations
- Shuffle automata and the growth of 1324-avoiding permutations
BibTeX
@misc{krityakierne2026distribution,
title = {{The Distribution of Double Deficiencies in Pattern-Avoiding Permutations}},
author = {Tipaluck Krityakierne and Thotsaporn Aek Thanatipanonda and Doron Zeilberger},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10492},
eprint = {2609.10492},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10492},
}
RIS
TY - UNPB
TI - The Distribution of Double Deficiencies in Pattern-Avoiding Permutations
AU - Tipaluck Krityakierne
AU - Thotsaporn Aek Thanatipanonda
AU - Doron Zeilberger
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10492
UR - https://arxiv.org/abs/2609.10492
AB - We study the distribution of the number of double deficiencies (DD) in permutations of length n avoiding one or two patterns of length 3. Using structural decompositions of these avoidance classes--together with a lattice-path decomposition in the 321-avoiding case--we derive functional equations and convolution-type recurrences that efficiently compute the corresponding double-deficiency generating functions in all but one single-pattern case. In the 321-avoiding permutations, the resulting generating function is algebraic; we derive exact formulas for the mean and variance and prove that the distribution is close in total variation to Bin(n-2,1/4), with an explicit convergence rate. We also identify a DD-preserving symmetry that yields DD-Wilf equivalences, reducing the number of two-pattern cases that need to be considered separately. For the resulting two-pattern classes, we obtain explicit recurrences, including C-finite relations.
ER -