ENUMERATION SCHEMES AND, MORE IMPORTANTLY, THEIR AUTOMATIC GENERATION

Doron ZEILBERGER^{1}

Towards the Virtual Combinatorialist

It is way too soon to teach our computers how to become full-fledged humans. It is even premature to teach them how to become mathematicians, it is even unwise, at present, to teach them how to become combinatorialists. But the time is ripe to teach them how to become experts in a suitably defined and narrowly focused subarea of combinatorics. In this article, I will describe my efforts to teach my beloved computer, Shalosh B. Ekhad, how to be an enumerator of Wilf classes.

Just like the Wright Brothers’ first flight, and Len Adelman’s first DNA computer (and perhaps like the first Fleischmann-Pons Cold Fusion experiment), the actual accomplishments are very meager. But I do hope to demonstrate feasibility, and jump-start a research area that is not quite part of AI, and not quite algorithmic combinatorics. It is something brand-new, let’s call it Artificial Combinatorics (AC). The closest analogy is Deep Blue, but instead of playing Chess, Shalosh will play a game called ‘Wilf-class enumeration’. It is still very far from beating the Kasparovs of the area (Miklos Bona, Alex Burstein, John Noonan, Frank Schmidt, Rodica Simion, Zved Stankova, Julian West, to name a few), but I am sure that the ultimate version will.

With all due respect to Wilf classes and Enumeration, and even to Combinatorics, the main point of this article is not to enhance our understanding of Wilf classes, but to illustrate how much (if not all) of mathematical research will be conducted in a few years. It goes as follow. Have a (as of now, human) mathematician get a brilliant idea. Teach that idea to a computer, and let the computer ‘do research’ using that idea.

Accompanying Software

In a sense, this article is a user’s manual for the Maple package WILF, available from my home-

page http://www.math.temple.edu/~zeilberg (click on Maple packages and programs, and

then download WILF). The empirical version of the rigorous WILF is HERB, also available there.

Enumeration Schemes

Suppose that we have to find a ‘formula’ (in the sense of Wilf[Wi], i.e. a polynomial-time algorithm) for computing a_{n} := |A_{n}|, where A_{n} is an infinite family of finite sets, parameterized by n. Usually A_{n} is a natural subset of a larger set B_{n}, and is defined as the set of members of B_{n} that satisfy a certain set of conditions C_{n}. For example if A_{n} is the set of permutations on {1, 2, …, n}, then B_{n} may be taken as the set of words of length n over the alphabet {1, 2, …, n}, and C_{n} can be taken as the condition: ‘no letter can appear twice’. A naive algorithm for enumerating A_{n} would be to actually construct the set, by examining the members of B_{n}, one by one, checking whether they satisfy C_{n}, and admitting those that qualify. Then a_{n}=Cardinality of A_{n}.

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu

http://www.math.temple.edu/~zeilberg . May 13, 1998. Supported in part by the NSF.

But a much better approach would be to find a structure theorem that expresses A_{n}, using unions, Cartesian products, and possibly complements, of well known sets. Failing this, it would be also nice to express A_{n}, recursively, in terms of A_{n−1}, A_{n−2}, …, and easy-to-count sets, getting a recurrence formula. Going back to the permutation example, Levi Ben Gerson ([L]) proved the structure theorem A_{n} ≡ {1, 2, …, n} × A_{n−1}, from which he deduced the recurrence a_{n} = na_{n−1}, enabling a polynomial-(in fact linear-) time algorithm for computing a_{i}, for 1 ≤ i ≤ n.

Alas, this is not always easy, and for many enumeration sequences, e.g. the number of self-avoiding walks, may well be impossible, and who knows, perhaps one day even provably impossible.

It is conceivable, however, that a combinatorial family A(n), does not possess a recursive structure by itself, but by refining it, using a suitable parameter, one can partition A(n) into the disjoint union:

A(n) = ⋃_{i=1}^{n} B(n, i) ,

and try and find a structure theorem for the two-parameter family B(n, i). This will imply a recurrence for the cardinalities b(n, i) := |B(n, i)|, that would enable a fast algorithm for a(n) = ∑_{i=1}^{n} b(n, i).

Sometimes, not even the B(n, i) suffice. Then we could try to partition B(n, i) into the following disjoint union:

B(n, i) = ⋃_{j=1}^{i−1} C_{1}(n, i, j) ∪ ⋃_{j=i+1}^{n} C_{2}(n, i, j) ,

and try to express C_{1}(n, i, j) and C_{2}(n, i, j) in terms of A(m), B(m, i′), C_{1}(m, i′, j′), and C_{2}(m, i′, j′), with m < n. One can keep going indefinitely. If this process halts after a finite number of refinements, then we have indeed a formula (in the sense of Wilf) for a(n).

Permutations with Forbidden Patterns; Wilf classes

A pattern of length k is a permutation of {1, 2, …, k}.

The reduction of a vector of distinct integers of length k is the pattern obtained by replacing the smallest element by 1, the second smallest by 2, …, the largest by k. For example, the reduction of 264 is 132.

A permutation π of length n, of an ordered set, is said to contain the pattern σ of length k if there are places i_{1} < … < i_{k}, such that π_{i_{1}}π_{i_{2}} … π_{i_{k}} reduces to σ. For example 51872463 contains the pattern 3421 (with i_{1} = 1, i_{2} = 3, i_{3} = 6, i_{4} = 8).

Our Goal is to investigate the following

Problem: Given a set of patterns P, study the sequence a(n; P) := |A(n; P)|, where A(n; P) is the set of permutations on {1, 2, …, n} that avoid the patterns of P.

We will sometimes write A(n) and a(n) instead of A(n; P) and a(n; P), where the P is implied from the context.

Of course a(n; ∅) ≡ n!, and a(n; {12}) ≡ 1. It is well known (see [We][K]) that a(n; {123}) = a(n; {132}) = C_{n}, where C_{n} = (2n)!/(n!(n + 1)! are the Catalan numbers.

Naively, it takes an exponential time to compute the first n terms of the sequence a(n; P). The best possible scenario is an explicit formula for the sequence. Failing this, it would be almost as nice to have a linear recurrence equation with polynomial coefficients (and hence inducting it in the hall of fame of P-recursive sequences).

Sometimes it happens that there exist two sets of patterns P and P′ such that a(n; P) = a(n; P′) for all n. If this happens for a non-trivial reason, we say that P and P′ belong to the same Wilf class.

The approach that I am going to investigate here, and that I taught Shalosh B. Ekhad, is to partition the set A(n; P) into a finite disjoint union of subsets, indexed by certain prefixes, and to try to deduce rigorously, certain recurrence relations between them, that would enable one to set up an enumeration scheme, that would lead to a polynomial-time algorithm for computing a(n; P). In the future it is hoped that these schemes could also be used to derive (once again rigorously) generating functions for the more refined quantities, that should lead to a constant-term expression for a(n; P), and that would make it decidable whether P and P′ belong to the same Wilf class.

Apology: The success rate of the present method, in its present state, is somewhat disappointing. Ekhad was able to reproduce the classical cases, and a few new ones, but for most patterns and sets of patterns, it failed to find a scheme (defined below) of a reasonable depth. But the present set-up for setting up a scheme could be modified and extended in various ways. We do believe that an appropriate enhancement of the present method would yield, if not a one-hundred-per-cents success rate, at least close to it.

The Most Trivial Non-Trivial Example

In order to illustrate the method, let’s work out in full detail, and in plain English, an Enumeration Scheme for the set of permutations avoiding the pattern 123.

Let A(n) be the set of such permutations. Break A(n) up into the union

A(n) = ∪_{i=1}^{n}A_{1}(n; i) ,

where A_{1}(n, i) are the set of 123-avoiding permutations on [1, n] that start with i, i.e.

A_{1}(n, i) := {π ∈ A(n); π_{1} = i} .

Let’s break up A_{1}(n; i) into the following disjoint union:

A_{1}(n, i) = ⋃_{h=1}^{i−1} A_{21}(n; h, i) ∪ ⋃_{j=i+1}^{n} A_{12}(n; i, j) ,

where for 1 ≤ i < j ≤ n,

A_{12}(n, i, j) := {π ∈ A(n); π_{1} = i , π_{2} = j} ,
A_{21}(n, i, j) := {π ∈ A(n); π_{1} = j , π_{2} = i} .

Now let’s look at a typical element π of A_{21}(n, i, j). It has π_{1} = j and π_{2} = i. Deleting the first entry (i.e. the j), and reducing, gives us a member σ of A_{1}(n − 1, i), since you can’t create trouble (i.e. a 123 pattern) by skipping town. FURTHERMORE, if you start out with any element σ of A_{1}(n − 1, i), make room for the j (by raising all members ≥ j by 1), and insert j at the very beginning, you can’t create new trouble, because the j is “body-guarded” by the i. Let me explain. If inserting j at the very beginning would have caused an undesirable 123-pattern, then of course, the “1” of the “123” would be j, but the “2” can’t be i (since j > i), hence in this hypothetical new 123 that the insertion of j at the very beginning would have created, the “2” would have been a certain σ_{a} and the “3” would be a certain σ_{b}, with 2 < a < b. But had that been the case, then i would have been an EVEN BETTER “1”!, because i < j, and σ_{1} < σ_{a} < σ_{b} would have already been a 123-pattern. It follows that A_{21}(n; i, j) is isomorphic to A_{1}(n − 1; i).

Now let’s examine A_{12}(n; i, j). If j < n, then n must be somewhere to the right, making ijn a 123-pattern. Hence A_{12}(n; i, j) is empty when j < n. On the other hand, if j = n, then deleting it creates a member of A_{1}(n − 1; i). Conversely, given any member of A_{1}(n − 1; i), inserting n right after the first entry (hence making n the second entry), can’t create a 123. Hence A_{12}(n; i, n) ≡ A_{1}(n − 1; i). Summarizing, we have the following structure:

A(n) = ⋃_{i=1}^{n} A_{1}(n; i) ,

A_{1}(n, i) := ⋃_{h=1}^{i−1} A_{21}(n; h, i) ∪ ⋃_{j=i+1}^{n} A_{12}(n; i, j) ,

A_{21}(n; i, j) ≡ A_{1}(n − 1; i) ,

A_{12}(n; i, j) ≡ \{ \begin{matrix}∅, & if j < n; \\ A_{1}(n − 1; i), & if j = n. \end{matrix}

Now let a(n) := |A(n)|, a_{1}(n; i) := |A_{1}(n; i)|, a_{12}(n; i, j) := |A_{12}(n; i, j)|, a_{21}(n; i, j) := |A_{21}(n; i, j)|. Taking cardinalities gives us the following scheme:

a(n) = ∑_{i=1}^{n} a_{1}(n; i) ,

a_{1}(n, i) := ∑_{h=1}^{i−1} a_{21}(n; h, i) + ∑_{j=i+1}^{n} a_{12}(n; i, j) ,

a_{21}(n; i, j) = a_{1}(n − 1; i)

a_{12}(n; i, j) = \{ \begin{matrix}0, & if j < n; \\ a_{1}(n − 1; i), & if j = n. \end{matrix}

Since a_{21} and a_{12} can be expressed in terms of a_{1}, the above can be condensed to

a(n) = ∑_{i=1}^{n} a_{1}(n − 1; i) ,

a_{1}(n, i) = (∑_{h=1}^{i−1} a_{1}(n − 1; h)) + a_{1}(n − 1; i) = ∑_{h=1}^{i} a_{1}(n − 1 ; h) ,

from which it follows that a_{1}(n; i) − a_{1}(n; i − 1) = a_{1}(n − 1; i). This recurrence and the obvious boundary conditions, a_{1}(n; 1) = 1 and a_{1}(n; n + 1) = 0, yield the explicit solution a_{1}(n; i) = \binom{n+i−2}{n−1} − \binom{n+i−2}{n}. Hence a(n) = a_{1}(n + 1, n + 1) = C_{n} = \binom{2n}{n}/(n + 1).

Introducing Prefix Schemes

The above example leads to the following definitions. Fix a set of patterns P. Let σ = σ_{1} … σ_{k} be any permutation of length k. For 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n, let

A_{σ}(n; P; i_{1}, …, i_{k}) := {π ∈ A(n; P) | π_{1} = i_{σ_{1}}, π_{2} = i_{σ_{2}}, …, π_{k} = i_{σ_{k}}} .

For example A_{132}(5; {1234, 1432}; 2, 3, 5) := {25314, 25341}.

The set of refinements of a permutation σ = σ_{1} … σ_{k} of length k is the set of k + 1 permutations of length k + 1 that have the property that deleting their last entry reduces to σ. We will denote the set of refinements of σ by Refinements(σ). For example, Refinements(312) = {3124, 4123, 4132, 4231}.

For any set of patterns P, and any prefix-permutation σ, we have the obvious recurrence

A_{σ}(n; P; i_{1}, …, i_{k}) = ⋃_{r=1}^{k+1} ⋃_{j=i_{r−1}+1}^{i_{r}−1} A_{σ^{(r)}}(n; P; i_{1}, …, i_{r−1}, j, i_{r}, …, i_{k}) ,  (∗)

where σ^{(r)} is that element of Refinements(σ) that ends with r. We agree that i_{0} = 0 and i_{k+1} = n. For example

A_{132}(n; P; i_{1}, i_{2}, i_{3}) = ⋃_{j=1}^{i_{1}−1} A_{2431}(n; P; j, i_{1}, i_{2}, i_{3}) ∪ ⋃_{j=i_{1}+1}^{i_{2}−1} A_{1432}(n; P; i_{1}, j, i_{2}, i_{3}) ∪

⋃_{j=i_{2}+1}^{i_{3}−1} A_{1423}(n; P; i_{1}, i_{2}, j, i_{3}) ∪ ⋃_{j=i_{3}+1}^{n} A_{1324}(n; P; i_{1}, i_{2}, i_{3}, j) .

Given a set of patterns, P, and a prefix permutation σ, it may happen that all the members of A_{σ}(n; P), for all n, must have either one or more of the properties i_{1} = 1, or i_{1} + 1 = i_{2}, i_{2} + 1 = i_{3}, …, i_{k} = n. Let J(σ) be the set of 0 ≤ r ≤ k such that i_{r} = i_{r+1} is forced for all members of A_{σ}(n; P). In the above example with P = {123}, we had J(12) = {2}, since every 123avoiding permutation that starts with i_{1}i_{2}, where i_{1} < i_{2}, must have i_{2} = n. Another Example: If P = {1234, 1324, 1243}, then J(2413) = {4}, since every member of A_{2413}(n; P; i_{1}, i_{2}, i_{3}, i_{4}) must have its second entry, i_{4} be equal to n, or else the n would be to the right of the fourth entry, that would cause i_{2}i_{4}i_{3}n to be an illegal 1324.

Consider all permutations. Let’s remember our goal. Given a set of patterns P, we want to count the number of permutations that avoid all the patterns of P. Let’s call these permutations lawabiding. Hence a permutation that has one or more occurrences of the patterns P should be called criminal. Obviously, deleting any entry of a law-abiding permutation (and reducing), gives rise to another law-abiding permutation. Hence given a prefix permutation σ = σ_{1} … σ_{k}, then for each place r (1 ≤ r ≤ k), we have the obvious inclusion:

F_{r}(A_{σ}(n; P; i_{1}, …, i_{k})) ⊂ A_{σ_{(r)}}(n − 1; P; i_{1}, …, i_{r−1}, i_{r+1} − 1, …, i_{k} − 1) ,  (Rodica)

where F_{r} is the injective mapping that consists of deleting i_{r} (wherever it is), and reducing, and σ_{(r)} is the permutation obtained from σ by deleting r and reducing.

BUT, it may happen that the inclusion (Rodica) is an equality. This leads to the following

IMPORTANT DEFINITION. Given a set of patterns P, and a prefix permutation σ, the place r (1 ≤ r ≤ k) is reversely deleteable if for all 1 ≤ i_{1} < … < i_{k} ≤ n,

F_{r}(A_{σ}(n; P; i_{1}, …, i_{k})) = A_{σ_{(r)}}(n − 1; P; i_{1}, …, i_{r−1}, i_{r+1} − 1, …, i_{k} − 1) .  (Julian)

We must find a way to know, a priori, by using logical reasoning, whether a place is reversely deleteable.

How can we be sure that inserting i_{r} in any permutation of A_{σ_{(r)}}(n − 1; P; i_{1}, …, i_{r−1}, i_{r+1} − 1, …, i_{k} − 1), in the appropriate place, is a safe thing to do? We must be assured that its insertion cannot cause any trouble. How can we be sure? We have to look at all the conceivable events that its insertion can cause, i.e. all the possible forbidden patterns of P, with one of its entries coinciding with the inserted i_{r}. If for each such possible scenario, in which i_{r} participates, we can logically deduce the existence of another event, in which i_{r} does not participate, then we are safe, since we are covered.

Example: Let P = {123}. For σ = 21, the place r = 1 is reversely deleteable, since suppose that inserting the i_{2} would have created a 123. Then there exist a and b in π such that i_{2}ab is a 123pattern. Had that been the case, then kal vakhomer, i_{1}ab is also a 123-pattern.

Another Example: Let P = {1234, 1324, 1243}. σ = 2413. We saw above that J(σ) = {4}, i.e. the permutations π that we are examining start with i_{2}ni_{1}i_{3} for some 1 ≤ i_{1} < i_{2} < i_{3} ≤ n. I claim that the first place, i.e. the i_{2} is reversely deleteable.

Let’s look at the kind of trouble the insertion of i_{2} at the beginning could cause. Event 1: There exist 4 < b < c < d ≤ n such that i_{2}π_{a}π_{b}π_{c} is a delinquent 1234. Then i_{2} can be bailed out by i_{1}, since i_{1}π_{a}π_{b}π_{c} would have been a bad event even before the insertion. Event 2: There exist 4 < b < c ≤ n such that i_{2}i_{3}π_{b}π_{c} is a delinquent 1234. Then i_{2} can be bailed out by i_{1}, since i_{1}i_{3}π_{b}π_{c} would have been a bad event even before the insertion. Event 3: There exist 4 < a < b < c ≤ n such that i_{2}π_{a}π_{b}π_{c} is a delinquent 1324. Then i_{2} can be bailed out by i_{1}, since i_{1}π_{1}π_{b}π_{c} would have been a bad event even before the insertion. Event 4: There exist 4 < b < c ≤ n such that i_{2}i_{3}π_{b}π_{c} is a delinquent 1324. Then i_{2} can be bailed out by i_{1}, since i_{1}i_{3}π_{b}π_{c} would have been a bad event even before the insertion. Event 5: There exist 4 < a < b < c ≤ n such that i_{2}π_{a}π_{b}π_{c} is a delinquent 1243. Then i_{2} can be bailed out by i_{1}, since i_{1}π_{1}π_{b}π_{c} would have been a bad event even before the insertion. Event 6: There exist 4 < b < c ≤ n such that i_{2}i_{3}π_{b}π_{c} is a delinquent 1243. Then i_{2} can be bailed out by i_{1}, since i_{1}i_{3}π_{b}π_{c} would have been a bad event even before the insertion. So any law-abiding permutation π, that starts with a triplet that reduces to 312 has an a priori guarantee that sticking an entry at the very front, that makes it have prefix that reduces to 2413, will not get the permutation π in trouble. Hence we can know for sure that, with P = {1234, 1324, 1243},

A_{2413}(n; P; i_{1}, i_{2}, i_{3}, i_{4}) = \{ \begin{matrix}∅, & if i_{4} < n; \\ A_{312}(n − 1 ; P; i_{1}, i_{3} − 1, i_{4} − 1), & if i_{4} = n. \end{matrix} .

Two ‘Trivial’ Examples Let’s rederive Levi Ben Gerson’s famous recurrence for a(n; ∅), i.e. a(n; ∅) = na(n − 1; ∅). First, let’s refine A(n; ∅) into

A(n; ∅) = ∪_{i_{1}=1}^{n}A_{1}(n; ∅; i_{1}) .

Now, note that r = 1 in σ = 1 is reversely deleteable, since inserting an i_{1} at the front can’t cause any trouble, since nothing is forbidden. Hence

A_{1}(n; ∅; i_{1}) ≡ A(n − 1; ∅) ,

from which follows that

a(n; ∅) = ∑_{i_{1}=1}^{n} a_{1}(n; ∅; i_{1}) = ∑_{i_{1}=1}^{n} a(n − 1; ∅) = na(n − 1; ∅) .

Next, let’s find a scheme when P = {12}, that is let’s try to compute a(n; {12}), the number of permutations on n objects with no occurrence of the pattern 12, i.e. the number of decreasing permutations. First, as always

A(n; {12}) = ⋃_{i_{1}=1}^{n} A_{1}(n; {12}; i_{1}) .

Now J(1) = {2}, since any 12-avoiding permutation must have i_{1} = n, or else i_{1}n would be a forbidden pattern. Also r = 1 is a reversely deleteable place, since inserting i_{1} = n at the very beginning of a permutation in A(n − 1; {12}) can’t possibly cause trouble. We hence have the following recurrence:

A(n; {12}) ≡ A(n − 1; {12}) ,

which implies that a(n; {12}) = a(n−1; {12}), and since a(0; {12}) = 1, we have proven, rigorously, that a(n; {12}) = 1, for all n > 0. A prefix scheme can be defined independently of sets of forbidden patterns P as follows. The Formal Definition of Prefix Scheme Definition: A PREFIX SCHEME is a five-tuple [Redu, Expa, A, B, C] such that:

(i) Redu is a finite set of permutations (of various lengths). (ii) Expa is another finite set of permutations (of various lengths). It must include the empty permutation ϕ. Expa and Redu are disjoint. (iii) A is a table assigning to each member σ = σ_{1} … σ_{k} of Redu, a place A[σ] in σ, i.e. an integer i between 1 and k. (iv) B is a table assigning to each permutation σ = σ_{1} … σ_{k} of Expa, its k + 1 refinements.

(v) C is a table that assigns to each member σ = σ_{1} … σ_{k} of Redu∪Expa a certain set J(σ), which is a (possibly empty) subset of {0, 1, 2, …, k}. (vi) For each σ ∈ Expa, each member B[σ] must belong to Expa ∪ Redu. For example, the following [Redu, Expa, A, B, C] is a prefix scheme: Redu = {12, 21}, Expa = {ϕ, 1}, A[12] = 1, A[21] = 1, B[ϕ] = {1}, B[1] = {12, 21}, C[12] = {2}, C[21] = C[1] = C[ϕ] = ∅. We are now ready to interface the abstract notion of prefix scheme to that of forbidden patterns. Another Important Definition: A Prefix Scheme [Redu, Expa, A, B, C] is an Enumeration Scheme for a set of forbidden patterns P, if the following conditions hold:

(i) For every σ ∈ Redu, let σ′ be the reduction of the permutation obtained from σ by deleting the entry at the place specified by A[σ]. The following property holds: If you take any permutation π that avoids the patterns in P, and that has a prefix that reduces to σ′, and insert a new entry right before the (A[σ]+1)^{th} place of π, in such a way that the new permutation has a prefix that reduces to σ, then that new permutation also avoids the patterns of P. In other words, the insertion is always safe.

(ii) Suppose that a permutation π of {1, 2, …, n}, avoids the patterns of P, and has a prefix that reduces to one of the permutations σ = σ_{1} … σ_{k} of Expa ∪ Redu, and the first k entries of π are i_{σ_{1}}i_{σ_{2}} … i_{σ_{k}}, where, of course, 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n. Then if 0 ∈ C[σ], we MUST have i_{1} = 1, and if k ∈ C[σ], we MUST have i_{k} = n, and for any other member j of C[σ], we MUST have i_{j} = i_{j+1}.

Implementing the Scheme

Once the computer (or, in simple cases, the human) has found a prefix-scheme for a set of patterns P, then we have a “formula” (in the Wilfian sense discussed above) for enumerating a(n; P).

If σ = σ_{1} … σ_{k} ∈ Expa, let σ^{(j)} (1 ≤ j ≤ k + 1), be that member of B[σ] that ends with j. We have, for 1 ≤ i_{1} < … < i_{k} ≤ n

a_{σ}(n; P; i_{1}, …, i_{k}) = ∑_{j=1}^{k+1} ∑_{r=i_{j−1}+1}^{i_{j}−1} a_{σ^{(j)}}(n; P; i_{1}, …, i_{j−1}, r, i_{j}, …, i_{k}) ,

where i_{0} = 0 and i_{k+1} = n + 1.

If σ = σ_{1} … σ_{k} is in Redu, let A[σ] = r. If C[σ] = ∅, then

a_{σ}(n; P; i_{1}, …, i_{k}) = a_{σ_{(r)}}(n − 1; P; i_{1}, …, i_{r−1}, i_{r+1} − 1, …, i_{k} − 1) ,  (Miklos)

where σ_{(r)} is the permutation obtained by reducing the permutation obtained from σ by deleting σ_{r}.

If J := C[σ] ≠ ∅ then (Miklos) holds whenever (i_{1}, …, i_{k}) “obeys J”, i.e. whenever i_{j} = i_{j+1} for all j ∈ J (recall that i_{0} = 1, i_{k+1} = n). Otherwise a_{σ}(n; P; i_{1}, …, i_{k}) = ∅.

Since the sets Redu and Expa are finite, the enumeration scheme is well-defined.

How to Find a Scheme

First a warning: there is no guarantee that a set of patterns P possesses a finite scheme. In fact, based on empirical evidence, most don’t (and if they did, their depth would be so large that the ‘polynomial’ in the “polynomial growth guarantee” would be of such a high degree as to make it almost as bad as exponential growth).

But that’s what’s so nice about non-trivial human research. If we know beforehand that we are guaranteed to succeed, then it is not research, but doing chores. So our “algorithm” is not known to halt. To make it a genuine algorithm, we make the maximal depth part of the input, and restrict the search to Prefix Schemes of bounded depth. If we fail, then the program returns 0.

The algorithm for looking for a Prefix Scheme for a given set of patterns P is a formalization of the procedure described above. The input is a set of patterns, and an integer, MaximalDepth.

We start with the empty permutation ϕ as belonging to Expa. Its only refinement is 1. Unless P = ∅, 1 would also belong to Expa. Its refinements are 12 and 21. We examine each prefix permutation σ, in turn, and see whether it has a non-empty J := C[σ] (forced relations), and equipped with that J, we look for a reversely deleteable place. This we do by looking at all the conceivable events that the place under consideration can participate in, and look at all the implied events, hoping to see amongst them an event that does not include the examined place. If indeed each and every possible calamity in which the examined place participates in, implies another event in which it does not participate in, (by using the transitivity of the order relation), then that place is indeed reversely deleteable.

If such a reversely deleteable place exists, then σ becomes a member of Redu, and the lucky place, that made it a member is recorded as A[σ]. If there are no such places, we reluctantly put σ in Expa, and find its refinements, that we store as B[σ]. We then examine these in turn, until we either get a prefix-permutation of length MaximalDepth + 1, in which case we sadly exit with 0, or all the offsprings of the member of Expa are in Expa ∪ Redu.

Important Remark: All the above deductions are made completely automatically by the computer. So we have (a very primitive) ‘Artificial Intelligence’.

Using the Maple package WILF

The procedure in the package WILF, that looks for Schemes for a set of patterns, is Scheme. The syntax is: “Scheme(Set Of Patterns,Maximal Depth)”. For example, to get a scheme for P = {123, 132}, type: “Scheme({[1,2,3],[1,3,2]},2);” (without the quotes, of course), followed, of course, by Carriage Return. Having found the scheme (let’s call it sch), to find the number of permutations on n objects avoiding the patterns P, you do “Miklos(n, sch); < CR >”. For example “Miklos(3,sch);<CR>” should yield 4. To get the first L terms of the sequence a(n; P) (after sch := Scheme(P; Depth) was successful for some Depth), do “SchemeSequence(sch,L);<CR>”. The package WILF could also try to guess (empirically, but perhaps rigorizably), a linear recurrence with polynomial coefficients. This procedure is called SchemeRecurrence. The reader should look up the on-line help.

SchemeF does what Scheme does, but more generally, by trying Scheme on all on the images of P under the dihedral group consisting of inverse, and reverse.

This paper’s website http://www.math.temple.edu/~zeilberg/WILF.html has numerous sample

input and output files.

The Maple package HERB

This is the non-rigorous counterpart of WILF. There a scheme is found empirically by checking (Julian) for small n, and extrapolating. It was written before the rigorous WILF, and helped a lot in developing the latter.

Future Directions

Prefix Schemes are equivalent to Suffix Schemes, but it should be possible to have mixed schemes. Also one may be even more creative in partitioning A_{σ}. Hopefully, a more general notion of scheme would be more successful. Also, it should be possible to empirically guess generating functions (or perhaps, redundant generating functions (in the sense of MacMahon)), for the A_{σ}, in Redu ∪ Expa, which, once guessed, are rigorously provable. This, in particular, would entail a constant-term expression for A(n; P), which, by using the WZ method, should lead to a rigorous derivation of the recurrence guessed by procedure SchemeRecurrence in WILF.

REFERENCES

[K] Donald E. Knuth, “The Art of Computer Programming”, vol.3, Addison-Wesley, Reading, MA, 1973. Second Edition 1997.

[L] Levi Ben Gerson, “Sefer Ma’asei Khosev”, 1321, Orange, France. [Extant printed version in: Gerson Lange, Frankfurt: Louis Golde, 1909.]

[We] Julian West, Generating trees and Catalan and Schröder numbers, Discrete Mathematics 146(1995), 247-262.

[Wi] Herbert S. Wilf, What is an Answer?, Amer. Math. Monthly 89(1982), 289-292.