INSENC

This package accompanies "Finding regular insertion encodings for permutation classes". In that paper you will find a description of the algorithm the package uses. It has been tested with Maple 11.

Download the package:

• plain text Maple source (version of August 17, 2011)

What INSENC can do:

If the class of permutations avoiding a particular set B of permutations has a regular insertion encoding (which INSENC will determine as soon as you type in B), then INSENC can compute the (necessarily rational) generating function for the class.

Example:

First, download the package. Then run Maple, and load the package by typing

> read INSENC;

Maple should respond with something to the effect of

INSENC: A Maple package for counting permutation classes with
regular insertion encodings.
Written by Vince Vatter, University of Florida
This version: August 17, 2011
Contains: insenc, suminsenc, rules2gf, rules2tm, tm2gf, tm2seq

For help with a procedure, run it with no arguments, e.g., insenc();

Now suppose that you want to count permutations avoiding both 4231 and 3142. Then at the prompt you should type

> R := insenc({4321,3142});

When entering permutations of length up to 9 you may enter them either as words - 4321 - or as lists - [4,3,2,1] - for longer permutations you must use lists. The computation will take a few seconds, after which Maple will answer with

> R := insenc({4321,3142});
[0] did not reduce.
4 states left to check
[1] has an IE-reducible element, in position 1
[1, 0] has an IE-reducible element, in position 1
[0, 1] did not reduce.
5 states left to check
[0, 2, 0, 1] did not reduce.
8 states left to check
[0, 2, 3, 1] has an IE-reducible element, in position 2
[2, 1] has an IE-reducible element, in position 1
[0, 1, 0] did not reduce.
13 states left to check
[2, 1, 0] has an IE-reducible element, in position 1
[2, 0, 1] has an IE-reducible element, in position 1
[0, 2, 1] did not reduce.
12 states left to check
[3, 2, 1] has an IE-reducible element, in position 1
[3, 0, 2, 1] has an IE-reducible element, in position 1
[3, 2, 0, 1] has an IE-reducible element, in position 1
[3, 0, 2, 0, 1] has an IE-reducible element, in position 1
[0, 2, 3, 0, 1] has an IE-reducible element, in position 2
[2, 0, 1, 0] has an IE-reducible element, in position 1
[0, 2, 1, 0] did not reduce.
11 states left to check
[3, 0, 2, 1, 0] has an IE-reducible element, in position 1
[3, 2, 1, 0] has an IE-reducible element, in position 1
[0, 2, 1, 3, 0] has an IE-reducible element, in position 4
[0, 2, 1, 0, 3] did not reduce.
9 states left to check
[0, 2, 1, 4, 0, 3] has an IE-reducible element, in position 2
[0, 2, 1, 0, 3, 0] did not reduce.
11 states left to check
[0, 2, 1, 0, 3, 4, 0] has an IE-reducible element, in position 5
[0, 2, 1, 0, 3, 4] has an IE-reducible element, in position 5
[0, 2, 1, 4, 0, 3, 0] has an IE-reducible element, in position 2
[0, 2, 1, 4, 3, 0] has an IE-reducible element, in position 2
[0, 2, 1, 3] has an IE-reducible element, in position 4
[0, 2, 0, 1, 0] did not reduce.
11 states left to check
[3, 0, 2, 0, 1, 0] has an IE-reducible element, in position 1
[3, 2, 0, 1, 0] has an IE-reducible element, in position 1
[0, 2, 3, 0, 1, 0] has an IE-reducible element, in position 2
[0, 2, 3, 1, 0] has an IE-reducible element, in position 2
[0, 2, 0, 1, 3, 0] did not reduce.
10 states left to check
[0, 2, 0, 1, 3] did not reduce.
11 states left to check
[0, 1, 2, 0] has an IE-reducible element, in position 2
[0, 1, 0, 2] did not reduce.
11 states left to check
[0, 1, 3, 0, 2] did not reduce.
12 states left to check
[0, 1, 2] has an IE-reducible element, in position 2
[0, 1, 0, 2, 0] did not reduce.
14 states left to check
[0, 1, 3, 0, 2, 0] did not reduce.
17 states left to check
[0, 1, 3, 2, 0] has an IE-reducible element, in position 2
[0, 2, 4, 0, 1, 3] has an IE-reducible element, in position 3
[0, 2, 4, 1, 3] has an IE-reducible element, in position 2
[0, 1, 3, 2] has an IE-reducible element, in position 2
[0, 1, 3, 4, 0, 2] has an IE-reducible element, in position 3
[0, 1, 3, 4, 2] has an IE-reducible element, in position 2
[0, 1, 0, 2, 3, 0] has an IE-reducible element, in position 4
[0, 1, 0, 2, 3] has an IE-reducible element, in position 4
[0, 2, 1, 4, 3] has an IE-reducible element, in position 2
[0, 1, 3, 4, 0, 2, 0] has an IE-reducible element, in position 3
[0, 1, 3, 4, 2, 0] has an IE-reducible element, in position 2
[0, 1, 3, 0, 2, 4, 0] has an IE-reducible element, in position 2
[0, 1, 3, 0, 2, 4] has an IE-reducible element, in position 2
[0, 2, 4, 0, 1, 3, 0] has an IE-reducible element, in position 3
[0, 2, 4, 1, 3, 0] has an IE-reducible element, in position 2
[0, 2, 0, 1, 3, 4, 0] has an IE-reducible element, in position 5
[0, 2, 0, 1, 3, 4] has an IE-reducible element, in position 5
R := table([[0, 2, 1, 0] =

    [[0, 2, 1, 0], [0], [0, 2, 1, 0], [0, 2, 1, 0, 3], [0, 2, 1, 0, 3, 0], [0, 2, 1]],

    [0, 2, 0, 1, 0] = [

    [0, 2, 0, 1, 0], [0, 1, 0], [0, 2, 0, 1, 0], [0, 2, 1, 0], [0, 2, 0, 1, 3, 0], [0, 2, 0, 1, 3]

    ], [0] = [[], [0], [0, 1], [0, 1, 0]], [0, 1, 0, 2] = [[0, 1, 3, 0, 2], [0, 2, 1]],

    [0, 2, 1, 0, 3, 0] = [[0, 2, 1, 0, 3, 0], [0, 2, 1, 0, 3], [0, 1, 3, 0, 2, 0], [0, 2, 1, 0]],

    [0, 2, 1] = [[], [0, 2, 1]], [0, 1, 3, 0, 2] = [[0, 1, 3, 0, 2], [0, 2, 1]],

    [0, 2, 0, 1] = [[0, 2, 1], [0, 1], [0, 2, 0, 1], [0, 2, 0, 1]], [] = [],

    [0, 2, 1, 0, 3] = [[0, 1, 3, 0, 2], [0, 2, 1]],

    [0, 2, 0, 1, 3, 0] = [[0, 2, 0, 1, 3, 0], [0, 2, 1, 0], [0, 2, 0, 1, 3, 0], [0, 2, 0, 1, 3]],

    [0, 1, 0, 2, 0] = [[0, 1, 3, 0, 2, 0], [0, 2, 1, 0], [0, 1, 0, 2, 0], [0, 1, 0, 2]],

    [0, 1, 3, 0, 2, 0] = [[0, 1, 3, 0, 2, 0], [0, 2, 1, 0], [0, 2, 0, 1, 3, 0], [0, 2, 0, 1, 3]],

    [0, 1, 0] = [[0], [0, 1, 0], [0, 2, 1, 0], [0, 2, 0, 1, 0], [0, 1, 0], [0, 1, 0, 2], [0, 1],

    [0, 1, 0, 2, 0]], [0, 2, 0, 1, 3] = [[0, 2, 0, 1, 3], [0, 2, 1]],

    [0, 1] = [[0, 2, 0, 1], [], [0, 1], [0, 2, 1]]

    ])

The procedure insenc has assigned a table to R, which contains a description of the regular language it found (actually, this table described the accepting automaton).

The procedure rules2gf will convert these rules into a generating function:

> rules2gf(R,x);
                                                          2
                                         (x - 1) (3 x - 1)
                                    - -------------------------
                                        2                     2
                                      (x  - 4 x + 1) (2 x - 1)

For help with a procedure, run it without arguments, e.g.,

> insenc();
insenc(B): Given a basis B, computes the "production rules" for the regular.
insertion encoding of Av(B), if Av(B) has a regular insertion encoding.
For example, try
	R := insenc({1324,4321});
	rules2gf(R,x);

< back to homepage