Finding regular insertion encodings for permutation classes
Journal of Symbolic Computation, 47 (2012), 259–265.
We describe a practical algorithm which computes the accepting automaton for the insertion encoding of a permutation class, whenever this insertion encoding is regular. This algorithm is implemented in the accompanying Maple package INSENC, which can automatically compute the rational generating functions for such classes.
Download the paper:
- from the journal (subscription required)
- ps
- source: source
Related links:
- The accompanying Maple package, INSENC.
- The 4321-, 1324-avoiding permutations are counted by sequence A165524 in the OEIS. This class is also part of a list on Wikipedia.
- The 4321-, 3142-avoiding permutations are counted by sequence A165530 in the OEIS. This class is also part of a list on Wikipedia.
- The {4321, 34512, 45123, 35412, 43512, 45132, 45213, 53412, 45312, 45231}-avoiding permutations from Bridget Tenner's paper “Repetition in reduced decompositions” are counted by sequence A191721 in the OEIS.
- The separable 321-avoiding permutations are counted by sequence A034943 in the OEIS.
- The separable 4321-avoiding permutations are counted by sequence A165521 in the OEIS.
- The separable 54321-avoiding permutations are counted by sequence A165522 in the OEIS.
- The separable 654321-avoiding permutations are counted by sequence A165523 in the OEIS.