Nonnesting permutations avoiding 123
Abstract
A nonnesting permutation of the multiset {1,1,2,2,...,n,n} is a word containing no subsequence abba with a distinct from b. Elizalde and Luo enumerated nonnesting permutations avoiding each set of two or more patterns of length three, and left open the enumeration of those avoiding the single pattern 123 (Problem 1 of their paper). We solve this problem. Writing cn for the number of nonnesting permutations of {1,1,...,n,n} avoiding 123 and C(z)=∑n≥ 0cnzn, we prove C(z) = 1 + z(1+U)/(2 − z(1+U)(1+V)), where V = 1+zV2 and U = 1+3z+zU2 are the formal power series branches with constant term 1. In particular C is algebraic of degree exactly 4 over ℚ(z), and cn ∼ (9+6√3)/8√π 6n n−3/2. The proof constructs a generating tree for these objects whose labels consist of two nonnegative integers, and applies the kernel method twice.
Related
- 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
- The Distribution of Double Deficiencies in Pattern-Avoiding Permutations
BibTeX
@misc{cowan2026nonnesting,
title = {{Nonnesting permutations avoiding 123}},
author = {Eric Cowan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.21680},
eprint = {2608.21680},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.21680},
}
RIS
TY - UNPB
TI - Nonnesting permutations avoiding 123
AU - Eric Cowan
PY - 2026
DA - 2026/09/05
PB - arXiv
DO - 10.48550/arxiv.2608.21680
UR - https://arxiv.org/abs/2608.21680
AB - A nonnesting permutation of the multiset {1,1,2,2,...,n,n} is a word containing no subsequence abba with a distinct from b. Elizalde and Luo enumerated nonnesting permutations avoiding each set of two or more patterns of length three, and left open the enumeration of those avoiding the single pattern 123 (Problem 1 of their paper). We solve this problem. Writing c_n for the number of nonnesting permutations of {1,1,...,n,n} avoiding 123 and C(z)=∑_n≥ 0c_nz^n, we prove C(z) = 1 + z(1+U)/(2 − z(1+U)(1+V)), where V = 1+zV^2 and U = 1+3z+zU^2 are the formal power series branches with constant term 1. In particular C is algebraic of degree exactly 4 over ℚ(z), and c_n ∼ (9+6√3)/8√π 6^n n^−3/2. The proof constructs a generating tree for these objects whose labels consist of two nonnegative integers, and applies the kernel method twice.
ER -