By Yonah Biers-Ariel
First Written: March 2, 2020; This version: March 2, 2020.
Abstract: This thesis demonstrates several applications of experimental methods to the enumeration of pattern-avoiding permutations. First, we introduce flexible schemes – a new extension of enumeration schemes. We show how a computer can find flexible schemes and use them to count permutations. We establish sufficient conditions for the existence of finite flexible schemes, and in particular show that they exist whenever finite enumeration schemes or regular insertion encodings do. Next, we combine enumeration schemes with structural arguments to give a new algorithm for counting 1342-avoiding permutations. We find a recurrence for the number of permutations avoiding four dashed patterns, and finally generalize Claude Lenormand’s "raboter" sequence. We have implemented all the algorithms described here in Maple and provide links to the Maple code in each section.
Produces the output: {[[], []], [[1], []], [[1, 2], []], [[2, 1], []], [[2, 3, 1], []], [[3, 1, 2], []], [[3, 2, 1], []], [[1, 2, 3], [[[0, 0, 0, 1], 0]], 3], [[1, 3, 2], [[[0, 0, 1, 1], 0]], 3], [[2, 1, 3], [[[0, 1, 0, 0], 0]], 1], [[2, 3, 1, 4], [[[0, 0, 0, 0, 1], 0], [[0, 0, 1, 0, 0], 0], [[0, 1, 0, 0, 0], 0]], 3], [[2, 3, 4, 1], [[[0, 0, 0, 0, 0], 4]], 1], [[2, 4, 3, 1], [[[0, 0, 0, 0, 1], 3], [[0, 0, 1, 0, 0], 4]], 2], [[3, 1, 2, 4], [[[0, 0, 0, 0, 1], 0], [[0, 0, 1, 0, 0], 0], [[0, 1, 0, 0, 0], 0]], 1], [[3, 1, 4, 2], [[[0, 1, 0, 0, 0], 0], [[0, 0, 0, 1, 1], 0]], 2], [[3, 2, 1, 4], [[[0, 0, 0, 0, 0], 2]], 1], [[3, 2, 4, 1], [[[0, 1, 0, 0, 0], 0], [[0, 0, 0, 1, 1], 0]], 1], [[3, 4, 1, 2], [[[0, 0, 0, 0, 1], 3], [[0, 0, 1, 0, 0], 4]], 4], [[3, 4, 2, 1], [[[0, 0, 0, 0, 1], 3], [[0, 0, 1, 0, 0], 4]], 4], [[4, 2, 3, 1], [[[0, 0, 0, 1, 1], 0], [[0, 1, 0, 0, 1], 3], [[0, 1, 1, 0, 0], 4]], 4], [[4, 3, 1, 2], [[[0, 0, 0, 1, 1], 2], [[0, 1, 0, 0, 1], 3], [[0, 1, 1, 0, 0], 4]], 2], [[4, 3, 2, 1], [[[0, 0, 0, 1, 1], 2], [[0, 1, 0, 0, 1], 3], [[0, 1, 1, 0, 0], 4]], 2]}
The input: SeqS({[[], []], [[1], []], [[1, 2], [[[0, 0, 1], 0]], 2], [[2, 1], [[[0, 0, 0], 2]], 1]}, 10);
Produces the output: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796
Produces the output: {[[[], {}], []], [[[1], {}], []], [[[1, 2], {}], []], [[[1, 2], {1}], []], [[[2, 1], {}], [[[0, 0, 0], 1]]], [[[1, 2, 3], {}], []], [[[1, 2, 3], {1}], []], [[[1, 3, 2], {}], [[[0, 0, 1, 0], 0], [[0, 0, 0, 0], 2]]], [[[1, 3, 2], {1}], []], [[[3, 1, 2], {}], [[[0, 0, 0, 0], 1]]], [[[3, 1, 2], {1}], [[[0, 0, 0, 0], 1]]], [[[3, 2, 1], {}], [[[0, 0, 0, 0], 1]]], [[[1, 2, 3, 4], {}], [[[0, 0, 0, 0, 0], 2]]], [[[1, 2, 3, 4], {1}], [[[0, 0, 0, 0, 0], 2]]], [[[1, 2, 4, 3], {}], [[[0, 0, 0, 1, 0], 0], [[0, 0, 0, 0, 0], 2]]], [[[1, 2, 4, 3], {1}], [[[0, 0, 0, 1, 0], 0], [[0, 0, 0, 0, 0], 2]]], [[[1, 3, 2, 4], {1}], [[[0, 0, 0, 0, 0], 2]]], [[[1, 3, 4, 2], {1}], [[[0, 0, 0, 0, 0], 0]]], [[[1, 4, 2, 3], {}], [[[0, 0, 0, 0, 0], 2]]], [[[1, 4, 2, 3], {1}], [[[0, 0, 0, 0, 0], 2]]], [[[1, 4, 3, 2], {1}], [[[0, 0, 0, 0, 0], 2]]], [[[4, 1, 2, 3], {}], [[[0, 0, 0, 0, 0], 1]]], [[[4, 1, 2, 3], {1}], [[[0, 0, 0, 0, 0], 1]]], [[[4, 1, 3, 2], {1}], [[[0, 0, 0, 0, 0], 1]]]}
The input: SeqS({[[[], {}], []], [[[1], {}], []], [[[1, 2], {}], [[[0, 0, 1], 0], [[0, 0, 0], 1]]], [[[2, 1], {}], [[[0, 0, 0], 1]]]},10);
Produces the output: 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975
Produces the output: 1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662
Produces the output: (30/29)*29^n-(9/4)*8^n-2^n+(3/2)*3^n+(12/5)*5^n-(35/22)*11^n
The input: GuessGeneralForm(b,n,2);
Produces the output: ((1/6)*b^2-(1/6)*b-1/3)*(b-1)^n+(-(1/6)*b^2+(1/3)*b-1/6)*b^n-b*(b-1)*(2*b-1)^n/(2*b-1)+(1/6)*(2*b^3+3*b^2-3*b-2)*(b^2+b-1)^n/(b^2+b-1)