Jay Pantone

John Wesley Young Research Instructor
Dartmouth College


Generating Permutations with Restricted Containers

with Michael Albert, Cheyne Homberger, Nathaniel Shar, and Vincent Vatter

We investigate a generalization of stacks that we call \(\mathcal{C}\)-machines. We show how this viewpoint rapidly leads to functional equations for the classes of permutations that \(\mathcal{C}\)-machines generate, and how these systems of functional equations can frequently be solved by either the kernel method or, much more easily, by guessing and checking. General results about the rationality, algebraicity, and the existence of Wilfian formulas for some classes generated by \(\mathcal{C}\)-machines are given. We also draw attention to some relatively small permutation classes which, although we can generate thousands of terms of their enumerations, seem to not have D-finite generating functions.


We are grateful to Mireille Bousquet-Mélou for suggesting a number of improvements to an earlier version of the paper, and in particular for pointing out the need to provide the analytic argument in the appendix and also to user Fan Zheng on MathOverflow whose comment on a question we posed there provided the inspiration for the aforementioned analytic argument.

OEIS Sequences
Open Questions