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.

- Journal: Journal of Combinatorial Theory, Series A
- arXiv: 1510.00269 [math.CO]

We are grateful to Mireille Bousquet-MÃ©lou for suggesting a number of improvements to an earlier version of the paper, and to the referees for their careful reading of this work.

- A257561 - \(\text{Av}(4231,4312,4321)\), known algebraic GF
- A106228 - \(\text{Av}(4123,4132,4213)\), known algebraic GF
- A257562 - \(\text{Av}(4123,4231,4312)\), 5000 terms known, GF unknown
- A165542 - \(\text{Av}(4123,4231)\), 1000 terms known, GF unknown
- A165545 - \(\text{Av}(4123,4312)\), 1000 terms known, GF unknown
- A053617 - \(\text{Av}(4231,4321)\), 600 terms known, GF unknown

- What can be said about the unknown generating functions for \(\text{Av}(4123,4231)\), \(\text{Av}(4123,4312)\), \(\text{Av}(4231,4321)\), \(\text{Av}(4123,4231,4312)\). Are they differentially algebraic? What are the growth rates of these classes?