FINLABEL


This package accompanies "Finitely labeled generating trees and restricted permutations". In that paper you will find a description of the algorithm the package uses, and a proof that it always works (well, under the hypothesis explained below). It has been tested with Maple 7, 8, and 9.

Download the package:

What FINLABEL can do:

Suppose that p is a permutation of length n-1. We think of p in one-line notation, that is, as a list of the numbers {1,2,...,n-1} in some order. A child of p is a permutation that can be obtained by inserting n somewhere into p. For example, 123645 is a child of 12345. In the paper mentioned above you will find a proof of the following result.

Theorem: Suppose that the set of permutations Q contains both a child of an increasing permutation and a child of a decreasing permutation. Then the tree of Q-avoiding permutations is isomorphic to a finitely labeled generating tree. (Terms defined in the paper mentioned above.) Moreover, under these conditions, FINLABEL can find the generating function that counts Q-avoiding permutations by length.

Example:

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

> read FINLABEL;

Maple should respond with something to the effect of

Warning, the protected names norm and trace have been redefined and unprotected

FINLABEL: A Maple package for finding finitely labeled generating trees
isomorphic to pattern avoidance trees.
Written by Vince Vatter (http://turnbull.mcs.st-and.ac.uk/~vince/)
This version: July 27, 2006
Thanks to Michael Albert and Doron Zeilberger for numerous suggestions.

Contains: finlabel, rules2gf, rules2tm, tm2gf, tm2seq

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

Now suppose that you want to find a generating tree isomorphic to T(123,3214,2143,15432), to verify Martin Klazar's result in On the least exponential growth admitting uncountably many closed permutation classes. At the prompt type

> R := finlabel({123,3214,2143,15432});

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

> R := finlabel({123,3214,2143,15432});
[3, 2, 1] can be labeled as [2, 1], |B|=4
[2, 1, 3] can be labeled as [1, 2], |B|=3
[2, 3, 1] can be labeled as [1, 2], |B|=2
[3, 1, 2] can be labeled as [2, 1], |B|=1
[4, 1, 3, 2] can be labeled as [2, 1], |B|=1
[6, 5, 1, 4, 3, 2] can be labeled as [2, 1], |B|=1
[5, 6, 1, 4, 3, 2] can be labeled as [1, 2], |B|=0
Construction of generating tree complete in 83.550    seconds.

R := table([[1, 4, 3, 2] = [[5, 1, 4, 3, 2]],

    [1, 3, 2] = [[1, 4, 3, 2], [2, 1]], [5, 1, 4, 3, 2] = [[2, 1], [1, 2]],

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

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

    ])

The procedure finlabel has assigned a table to R, which contains a description of the tree found. This particular tree has root [1] and follows the rules

[1] -> [2,1][1,2]
[1,2] -> [2,1][1,3,2]
[2,1] -> [2,1][1,2][1,2]
[1,3,2] -> [1,4,3,2][2,1]
[1,4,3,2] -> [5,1,4,3,2]
[5,1,4,3,2] -> [1,2][2,1]

You might notice that we don't need both labels [1] and [5,1,4,3,2], since they have the same children. FINLABEL only promises to find you a generating tree, not necessarily the most efficient one.

Instead of the generating tree, you probably want the generating function for the number of {123,3214,2143,15432}-avoiding n-permutations. You can find this by using the procedure rules2gf:

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

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

> finlabel();
finlabel(Q): Inputs a set of patterns and outputs a Maple table containing
the succession rules describing a generating tree isomorphic to the tree of
permutations avoiding all the patterns in Q.
To convert a set of succession rules to a transfer matrix, see rules2tm.
To convert a set of succession rules to a generating function, see rules2gf.
For example, try
        R := finlabel({132,3241});
        rules2gf(R,x);