WILFPLUS


WILFPLUS is designed to find (Wilfian) formulas for restricted permutations. It is described in the paper "Enumeration schemes for restricted permutations."

It is an extension Doron Zeilberger's package WILF, which is described in his paper "Enumeration schemes, and more importantly, their automatic generation." (Another package of mine, FINLABEL, was a special case of WILF.)

WILFPLUS has been tested with Maple 7, 8, and 9.

Download the package:

Example:

Download the package, run Maple, and load the package by typing 
> read WILFPLUS;
Maple will then say 
Warning, the protected names norm and trace have been redefined and unprotected

WILFPLUS: A Maple package to find formulas for restricted permutations.
Written by Vince Vatter, Dartmouth College
This version: August 29, 2009
Contains: wilfplus, scheme2seq

For help with a procedure, run it with no arguments, e.g.,
	wilfplus();	or	scheme2seq();
Now let's suppose you want to find a formula for {1342,2431}-avoiding permutations, which were first counted by Miklós Bóna in The permutation classes equinumerous to the smooth class. Then at the prompt you should type 
> S := wilfplus({1342,2431});
When entering short permutations, you may use either words - 1342 - or lists - [1,3,4,2] - but if your permutation has 10 or more elements, you must of course enter it as a list (and wait a long time). By default, WILFPLUS will also try to find a scheme for symmetries of this class (to turn this option off, see the help). Since WILFPLUS can find a scheme for the permutations avoiding B if and only if it can find a scheme for the symmetries avoiding the reverse of B, it only tries one of each pair. In this case, you should see 
Checking all 3 symmetries of the set of forbidden patterns

Avoided patterns: {[2, 4, 3, 1], [1, 3, 4, 2]}
Now checking permutations of length 1, 1 permutation to check.
Of the permutations checked, 0 had a ES-reducible element and 1 did not.
The permutations that did not reduce are: {[1]} 

Avoided patterns: {[1, 4, 2, 3], [4, 1, 3, 2]}
Now checking permutations of length 1, 1 permutation to check.
Of the permutations checked, 0 had a ES-reducible element and 1 did not.
The permutations that did not reduce are: {[1]} 

Avoided patterns: {[4, 2, 1, 3], [3, 1, 2, 4]}
Now checking permutations of length 1, 1 permutation to check.
Of the permutations checked, 0 had a ES-reducible element and 1 did not.
The permutations that did not reduce are: {[1]} 

Avoided patterns: {[2, 4, 3, 1], [1, 3, 4, 2]}
Now checking permutations of length 2, 2 permutations to check.
Of the permutations checked, 0 had a ES-reducible element and 2 did not.
The permutations that did not reduce are: {[1, 2], [2, 1]} 

Avoided patterns: {[1, 4, 2, 3], [4, 1, 3, 2]}
Now checking permutations of length 2, 2 permutations to check.
Of the permutations checked, 0 had a ES-reducible element and 2 did not.
The permutations that did not reduce are: {[1, 2], [2, 1]} 

Avoided patterns: {[4, 2, 1, 3], [3, 1, 2, 4]}
Now checking permutations of length 2, 2 permutations to check.
Of the permutations checked, 0 had a ES-reducible element and 2 did not.
The permutations that did not reduce are: {[1, 2], [2, 1]} 

Avoided patterns: {[2, 4, 3, 1], [1, 3, 4, 2]}
Now checking permutations of length 3, 6 permutations to check.

SUCCESS! The construction of an enumeration scheme for the permutations avoiding
	{[2, 4, 3, 1], [1, 3, 4, 2]}
is complete. The computation took 7.45 seconds

S := [{[2, 4, 3, 1], [1, 3, 4, 2]}, [[1, 2, 3], 2, {}], [[3, 1, 2], 2, {[0, 0, 2, 0]}],

    [[2, 3, 1], 1, {[0, 1, 0, 0]}], [[3, 2, 1], 2, {}], [[1, 3, 2], 2, {[0, 0, 1, 0]}],

    [[2, 1, 3], 2, {[0, 2, 0, 0]}]]
The procedure wilfplus has now saved an enumeration scheme for these permutations in S. You now also use the scheme2seq command to get the number of {1342,2431}-avoiding permutations: 
> scheme2seq(S,13);
  1, 2, 6, 22, 88, 366, 1552, 6652, 28696, 124310, 540040, 2350820, 10248248

Sure enough, this agrees with the sequence, number A032351 in the On-Line Encyclopedia of Integer Sequences.

For more information on the functions, run them without arguments, e.g., 

> wilfplus();
wilfplus: This procedure can either be called with a set of forbidden patterns,
	or with a partial scheme (more on this below).
Optional arguments:
	maxdepth=M : tell wilfplus only to run up to depth M
	writeto=FILE : log all output to file named FILE
		(You may need to put the filename in quotes.)
	appendto=FILE : same as above, but append rather than overwrite
	nosyms : tell wilfplus not to try symmetries of the forbidden patterns
	verbose : tell wilfplus to run in verbose mode
	returnpartial : tell wilfplus to return a partial scheme if maxdepth is
		reached, so that computation might be resumed later.
	partscheme=PS : tell wilfplus to resume computation
		on the partial scheme PS
Examples:
	wilfplus(123);
	wilfplus({132,3421},nosyms);
	wilfplus({1342,1432},verbose,maxdepth=7);
	wilfplus({1342,2431},maxdepth=3,verbose,nosyms,writeto=smoothperms.txt);

	PS := wilfplus({1342,2431},maxdepth=2,returnpartial,nosyms):
	wilfplus(partscheme=PS,maxdepth=3);

More examples: