Combinatorial Exploration: An algorithmic framework for enumeration

Memoirs of the American Mathematical Society, Volume 317, Number 1611, 2026

Michael, Christian, Anders, Émile, Jay and Henning

A combinatorial class is often studied by finding a combinatorial specification for it, which is a description of the class in terms of simpler classes, and perhaps recursions to smaller instances of the original class. In this paper we describe how to automate the discovery of combinatorial specifications of combinatorial classes. This is achieved by first generating a universe of interconnected combinatorial classes and then searching for a specification inside this universe. The main application is in the area of permutation patterns, but other domains such as, set partitions, strings, polyominoes and lattice paths are discussed.

Download the paper

• Memoirs of the AMS
• arXiv
• Christian’s PhD thesis: Finding structure in permutation sets

Presentations

Later work (last updated 3 October 2026)

• C. Bean, A. Bernini, M. Cervetti and L. Ferrari, On the generating functions of pattern-avoiding Motzkin paths, J. Symbolic Comput. 113 (2022). Uses Combinatorial Exploration, through its implementation comb_spec_searcher, to find combinatorial specifications for pattern-avoiding Motzkin paths.
• C. Bean, É. Nadeau, J. Pantone and H. Úlfarsson, Using large random permutations to partition permutation classes, Pure Math. Appl. 30 (2022). Uses the specifications found by Combinatorial Exploration to generate large random permutations in a class uniformly, and clustering to split the class into subclasses.
• L. Nabergall, Enumerative perspectives on chord diagrams, PhD thesis, University of Waterloo (2022). Extends Combinatorial Exploration to chord diagrams, with decomposition strategies mostly based on those for permutation classes, and enumerates several classes of chord diagrams for the first time.
• M. Bóna and J. Pantone, Permutations avoiding sets of patterns with long monotone subsequences, J. Symbolic Comput. 116 (2023). Uses Combinatorial Exploration to compute hundreds of terms of the counting sequence of one of the classes studied, giving strong numerical evidence for its growth rate.
• É. Nadeau, Multivariate combinatorial exploration with regular strategies, PhD thesis (2023). Extends Combinatorial Exploration to problems that involve additional statistics, and introduces the fusion strategy for permutation classes.
• C. Bean, É. Nadeau, J. Pantone and H. Úlfarsson, Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding, Electron. J. Combin. 31 (2024). Uses Combinatorial Exploration to enumerate hundreds of classes defined by avoiding a partially ordered pattern of size 5, resolving conjectures of Gao and Kitaev and of Chen and Lin.
• R. Brignall and V. Vatter, Uncountably many enumerations of well-quasi-ordered permutation classes, Combinatorial Theory 6 (2026). Its heatmaps were drawn from permutations sampled uniformly at random with Combinatorial Exploration.
• V. Vatter, An assortment of problems in permutation patterns: unimodality, equivalence, derangements, and sorting, preprint (2026). Reports that Pantone proved a conjecture of Atkinson on the generating function of a permutation class using Combinatorial Exploration.
• C. Bean, A. J. Guttmann and J. Pantone, Enumerating pattern-avoiding involutions using Combinatorial Exploration, preprint (2026). Adapts Combinatorial Exploration to involutions, finding the algebraic generating functions of two Wilf-equivalence classes of involutions avoiding a pattern of length 4.
• All citing papers on Google Scholar (31)