Counting the permutation classes Av(B) for every basis B of size 4 patterns — almost

As you can see below, there are almost 17 million such classes. But we can make this tractable by first cutting away symmetric bases (step 2). Then we use the insertion encoding of Albert, Linton and Ruškuc to trim away classes with a regular insertion encoding and therefore a rational generating function (step 3). Finally we remove classes with finitely many simples (step 4). Brignall, Ruškuc and Vatter proved that whether a class has finitely many simples is decidable, Bassino, Bouvel, Pierrot and Rossin gave an algorithm that decides it, and Arnar Bjarni Arnarson implemented the algorithm in Permuta.

We ran Combinatorial Exploration on every class left after step 3, all 2,897 that are not insertion encodable, and it found a specification for each of them except Av(1324) and its reverse, Av(4231) (see the Combinatorial Exploration paper). Step 4 is shown for the picture.

1. All subsets of S₄
16,777,215
every nonempty set of length-4 patterns
2. Up to symmetry
2,139,263
one basis per symmetry class
3. Not insertion encodable in any direction
2,897
1 in 738 of step 2
4. Also infinitely many simples
1,123
39% of step 3

Each step has its own bar, from the left edge to its count on a log scale, so every tenfold adds the same length. In each row the bars are steps 1 to 4, from the top. Steps 2 to 4 count one basis per symmetry class. Steps 3 and 4 cut by properties that pass to subclasses: if Av(B) has one, so does Av(B ∪ C) for every set C of patterns. So a basis cut here never needs patterns of length 5 added.

How the counts were made

Step 2 by Burnside's lemma over the 8 symmetries, which have 24, 12, 12, 16, 17, 17, 9 and 9 cycles on S₄: (2²⁴ + 2·2¹⁷ + 2¹⁶ + 2·2¹² + 2·2⁹)/8 = 2,139,264 orbits, the empty set among them.

Step 3 with Permuta's test for a regular insertion encoding, applied to each of the 8 symmetric images of every basis. These come to two tests, from the right and from the top, which is Permuta's is_insertion_encodable.

Step 4 with Permuta's test for finitely many simple permutations, on each of the 2,897 bases; it decided every one.

Adding patterns of length 5

The next step is every class Av(B) whose basis B = B4 ∪ B5 has patterns of length 4 and of length 5, at least one of each. No pattern of B5 contains one of B4, as it would be redundant. Each pattern of length 4 lies in 17 permutations of length 5, so it leaves 103 to add, and the sizes of B run from 2 to 104. The steps are those above, now for B itself.

1. All bases
≈ 2.44×10³²
sizes 2 to 104
2. Up to symmetry
≈ 3.04×10³¹
one basis per symmetry class
3. Not insertion encodable
≈ 4.57×10²³
sizes 2 to 77
4. Also infinitely many simples
8,927,534
sizes 2 to 5 so far

Each step has its own bar, from the left edge to its count on a log scale, so every tenfold adds the same length. In each row the bars are steps 1 to 4, from the top. Steps 2 to 4 count one basis per symmetry class. Step 4 is counted up to size 5 so far.

References

  1. Michael H. Albert, Steve Linton and Nik Ruškuc. The insertion encoding of permutations. Electronic Journal of Combinatorics 12 (2005), #R47. doi:10.37236/1944
  2. Robert Brignall, Nik Ruškuc and Vincent Vatter. Simple permutations: decidability and unavoidable substructures. Theoretical Computer Science 391 (2008), 150–163. doi:10.1016/j.tcs.2007.10.037
  3. Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot and Dominique Rossin. An algorithm for deciding the finiteness of the number of simple permutations in permutation classes. Advances in Applied Mathematics 64 (2015), 124–200. doi:10.1016/j.aam.2014.12.001