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.

Maple packages

• Flexible_Scheme.mpl (or Flexible_Scheme.txt), a Maple package to find and use flexible enumeration schemes.

• Flexible_Covincular_Scheme.mpl (or Flexible_Covincular_Scheme.txt), a Maple package to find and use flexible enumeration schemes for covincular (and thus also vincular) patterns.

• 1423Avoid.mpl (or 1423Avoid.txt), the implementation of a fast recurrence to count 1423-avoiding (and equivalently 1342-avoiding) permutations using enumeration schemes and structure arguments.

• raboter.mpl (or raboter.txt), a Maple package for conjecturing and proving explicit formulas for sums of terms in generalized "raboter" sequeunces.

Sample Input and Output for Flexible_Scheme.mpl

The input: HasScheme({[1,2,3,4],[2,4,1,3]},4,2);

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

Sample Input and Output for Flexible_Covincular_Scheme.mpl

The input: HasScheme({[[1, 3, 4, 2], {1, 2}], [[1, 3, 4, 2], {2, 3}]}, 4, 2);

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

Sample Input and Output for 1423Avoid.mpl

The input: seq(a(n, n), n = 1 .. 10);

Produces the output: 1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662

Sample Input and Output for raboter.mpl

The input: SumPowers(3, n, 3);

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)