Uncountably many enumerations of well-quasi-ordered permutation classes
Robert Brignall, Vincent R. Vatter · Combinatorial Theory · 2026
We construct an uncountable family of well-quasi-ordered permutation classes, each with a distinct enumeration sequence. This disproves a conjecture that all well-quasi-ordered permutation classes have algebraic generating functions, and in fact shows that many such classes lack D-finite or D-algebraic generating functions. Our construction is based on an uncountably large collection of factor-closed, well-quasi-ordered binary languages due to Pouzet.Mathematics Subject Classifications: 05A05, 05A15, 06A07Keywords: Generating functions, permutation classes, well-quasi-order