On Vince Vatter’s Brilliant Extension of Doron Zeilberger’s Enumeration Schemes for Herb Wilf’s Classes

Doron ZEILBERGER^{1}

Retail vs. Wholesale Enumeration

An enumerative retailer studies one problem at a time. On the other hand, an enumerative wholesaler studies a family of problems, and tries to design algorithms that can be implemented to solve lots and lots of problems from that family.

Doron Zeilberger’s Original Enumeration Schemes

In [Z1] I tackled the problem of enumerating Wilf classes, i.e. finding “schemes” for enumerating sets of permutations avoiding a given set of patterns. Alas, the success rate was rather disappointing.

Vince Vatter’s Brilliant Extension

In [V], my brilliant disciple, Vince Vatter, introduced a far-reaching extension: gap vectors! This made the success rate much higher!

Zeilberger’s original approach

My original approach was to teach the computer some elementary ‘logical reasoning’, and find enumeration schemes that way. This was done in a Maple package (still available from my website) called WILF. To check the ‘logical’ program, I also wrote an empirical program, called HERB. The Maple package HERB found enumeration schemes by testing them for permutations of size n ≤ N_{0}, where N_{0} was some positive integer chosen by the user. But to rigorously prove the validity of the candidate enumeration schemes we still need the ‘logical’ program WILF, since the empirical program, HERB, is just that, empirical! OR IS IT?.

Digression: How Gil Kalai almost flunked his High-School Matriculation Math Exam

A few weeks ago, the great combinatorist and geometer, Gil Kalai, visited Rutgers in order to give a colloquium talk (that by the way was excellent). Before the talk we chatted a bit, and I was kvetching that a recent paper of mine ‘Automatic CounTilings’[Z2], was stupidly and narrowmindedly rejected by Journal of Combinatorial Theory-Series A, and my appeal, to Advisory Board member Mireille Bousquet-Mélou, to reconsider, was unsuccessful.

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg . First version: Dec. 29, 2006. This version: March 28, 2007 [incorporating Lara Pudwell’s and Vince Vatter’s referee reports available from http://www.math.rutgers.edu/~zeilberg/mamarim/ mamarimhtml/vatter.html] . Accompanied by Maple package VATTER downloadable from Zeilberger’s website.

Supported in part by the NSF.

One of the things that the referee, and apparently also Bousquet-Mélou, didn’t get, was my “almost” proof of Kasteleyn’s famous formula for the number of dimer tilings of a rectangle. It was based on the observation that by some ‘handwaving argument’ (that is nevertheless fully rigorous) checking a statement for finitely many cases implies it in general. When Gil heard that, he immediately exclaimed:

“This kind of argument almost made me flunk my high-school graduation math exam. I was asked to prove a certain trig identity, (like cos 2θ = 2 cos^{2} θ − 1) and I verified it for θ = 0, π/4, π/2. Since both sides are Laurent polynomials in e^{2iθ} of degree 1 and low-degree −1, this empirical proof is perfectly rigorous, but the stupid examiner didn’t understand.”

But I shouldn’t scorn the anonymous examiner, or the anonymous referee, (and the non-anonymous editor, Mireille Bousquet-Mélou) too much, since I, myself, committed the same stupidity, by not realizing that my ‘empirical’ Maple package HERB is easily rigorizable. It was Vince Vatter[V] who noticed it first. For each and every putative enumeration scheme (see below) there exists an easily computable N_{0}, such that verifying the correctness of the enumeration scheme for all n ≤ N_{0}, proves its validity in general. Furthermore, the same holds for his more general version of enumeration schemes, that feature gap vectors. That was the approach taken in his own Maple implementation, WILFPLUS, described in [V].

OK, Empirical Proofs Can (Often) Be Made Rigorous, But Is It the Most Efficient Way?

But the “N_{0} approach” is, like everything else, yet another algorithm. Conceptually, it may be the simplest, and ‘modulo routine checking’ the shortest, but that ‘routine checking’ may take a long time. So if Gil Kalai would have had to prove that cos^{1000} 2θ = (2 cos^{2} θ−1)^{1000} using the empirical approach, he would have had to plug-in many more values. With a little bit of “cheating”, using logical reasoning, he could have proved the first identity as before, and then use the rule A = B implies A^{n} = B^{n}, that by the way, can be easily taught to a computer.

A “Logical” Approach to Vatter’s Gapped Enumeration Schemes

The purpose of the present article, implemented in the Maple package VATTER, is to adapt the “logical” approach of [Z1], as implemented in the original Maple package WILF, to Vatter’s gappedextension of enumeration schemes. It appears that VATTER runs considerably faster than Vatter’s

WILFPLUS.

Definition, Examples, Definition, Examples, Definition, Examples, …

Definition: The reduction of a finite sequence of different numbers is the permutation obtained by replacing the smallest entry by 1, the second smallest entry by 2, …, and the largest entry by the sequence’s length. In other words, if the length of the sequence is k, then the i^{th}-smallest entry is replaced by i, for 1 ≤ i ≤ k.

Examples of reduction: The reduction of 6283 is 3142. The reduction of πγeϕ is 4132. Definition: The Children of a permutation π of {1, …, k} are all the k + 1 permutations of {1, …, k + 1} for whom the permutation obtained by chopping the last entry reduces to π. Examples of Children: The set of children of 132 is {2431 , 1432 , 1423 , 1324 } . Definition: A VZ-triple is a triple [π, G, T] where π is a permutation of {1, …, k} for some nonnegative integer k, G is a (possibly empty) set of vectors of non-negative integers of length k + 1, and T is (a possibly empty) subset of {1, …, k}. Examples of VZ-triples :

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

Definition: Let V be a finite set of VZ-triples, and let P be the set of first components of its triples. V is an abstract VZ- enumeration scheme if the following conditions hold:

1. If [π, G, T] ∈ V and T = {} then all the children of π are in P.

2. If [π, G, T] ∈ V and T ≠ {} then T has at least one member, let’s call it t, such that the reduction of the permutation obtained from π by deleting its t^{th} entry belongs to P. An Example of an abstract enumeration scheme:

{ [[ ], {}, {}] , [ 1, {}, {}] , [ 12 , {[0, 0, 1]}, {2}] , [ 21 , {}, {1}] } .

Definition Let {S(n), n ≥ 0 } be a sequence of sets, where S(n) is a set of permutations of {1, …, n}. For any permutation π = π_{1} … π_{k} , and any increasing k-tuple of integers (i_{1}, …, i_{k}), where 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n, let S(n)[π](i_{1}, …, i_{k}) be the set of members of S(n) whose first k entries are (in that order) i_{π_{1}} … i_{π_{k}} (and hence their prefix of length k reduces to π and consists of {i_{1}, …, i_{k}}). An abstract enumeration scheme V becomes a concrete enumeration scheme for {S(n)} if

1. For any member of V, [π = π_{1} … π_{k} , G , T ], and for any g ∈ G, the following holds. If i_{1}−1 ≥ g_{1} AND i_{2}−i_{1}−1 ≥ g_{2} AND … AND i_{k}−i_{k−1}−1 ≥ g_{k} AND n+1−i_{k}−1 ≥ g_{k+1} ,

(GapConditions(g))

then S(n)[π](i_{1}, …, i_{k}) is the empty set.

2. For any member of V, [π = π_{1} … π_{k} , G , T ], the following holds.

For every element t ∈ T, and every n ≥ k, and every increasing sequence of integers 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n that do not obey any of (GapConditions(g)) (g ∈ G),

|S(n)[π](i_{1}, …, i_{k})| = |S(n)[π′](i′_{1}, …, i′_{k−1})| .

where π′ is the reduction of the permutation of length k − 1 obtained by deleting π_{t} from π, and (i′_{1}, …, i′_{k−1}) is the reduction of of the vector obtained from (i_{1}, …, i_{k}) by deleting i_{π_{t}}.

Remark: If V is a concrete enumeration scheme for {S(n)}, then we have a polynomialtime algorithm for enumerating the sequence s_{n} := |S(n)|. We need to compute for each [π = π_{1}, …, π_{k}, G, T] ∈ V and for each sequence 1 ≤ i_{1} < … < i_{k} ≤ n (there are \binom{n}{k} = O(n^{k}) such sequences of course) the number of elements of S(n)[π](i_{1}, …, i_{k}). If at least one of the GapConditions(g), (g ∈ G) is satisfied, we know immediately that it is 0. If T ≠ {} and t ∈ T is such that the reduction of π_{1}, …, π_{t−1}π_{t+1}, … π_{k} belongs to P, then it is |S(n)[π′](i′_{1}, …, i′_{k−1})|. Finally if T = {}, we express this quantity in terms of the children of the permutation and the “children” of (i_{1}, …, i_{k}). By the definition of “abstract enumeration scheme”, this will give an effective way of computing all the |S(n)[π][i_{1}, …, i_{k}]|, and in particular, our object of desire, |S(n)[ ][ ]|, which is |S(n)| of course.

Restricted Permutations

Definition: A pattern of length a is a permutation p_{1} … p_{a} of {1, 2, …, a}. (used in the context below).

Definition: A permutation σ = σ_{1} … σ_{n} contains the pattern p = p_{1} … p_{a}, if there exist 1 ≤ j_{1} < j_{2} < … < j_{a} ≤ n such that σ_{j_{1}}σ_{j_{2}} … σ_{j_{a}} reduces to p.

Example of containment: 451362897 contains the pattern 2134 since (among other possibilities) the subpermutation of the former with j_{1} = 2, j_{2} = 4, j_{3} = 5, j_{4} = 7 yields 5368 that reduces to 2134.

Definition: A permutation σ = σ_{1} … σ_{n} avoids the pattern p = p_{1} … p_{a}, if it does not contain it.

Example of avoiding a pattern: The permutation 45321 avoids the pattern 132, since none of the \binom{5}{3} subsequences of 45321, of length 3, which are:

453, 452, 451, 432, 431, 421, 532, 531, 521, 321 ,

reduce to 132. (They reduce to 231, 231, 231, 321, 321, 321, 321, 321, 321, 321 respectively).

Definition: A permutation σ = σ_{1} … σ_{n} avoids the set of patterns P, if it avoids every pattern p ∈ P.

Example of avoiding a set of patterns: The permutation 45321 avoids the set of patterns P = \{123, 132, 312\}, since none of the \binom{5}{3} subsequences of 45321, to wit:

453, 452, 451, 432, 431, 421, 532, 531, 521, 321

reduces to one of the members of P.

Given any set of patterns P, our goal is to try and find a concrete enumeration scheme for the sequence of sets of permutations {S(n)} where S(n) is the set of permutations of {1, 2, …, n} that avoid all the patterns of P.

How to Find Gap Vectors?

Given a prefix-permutation, π = π_{1} … π_{k}, and a vector g = [g_{1}, …, g_{k+1}], we want to see whether (GapConditions(g)) guarantee that the corresponding set is empty. One way to do it, is to look at a putative permutation obeying the gap conditions. If all the conditions (for g) hold it means that there is a “gap” of size g_{1} between 0 and i_{1}, and a “gap” of size g_{2} between i_{1} and i_{2}, …, and a gap of size g_{k+1} between i_{k} and n. Since everything depends on the reduction we can rename i_{1} to be 1, i_{2} to be 2, …, i_{k} to be k and

the putative members of the gap between 0 and i_{1} by

\frac{1}{g_{1} + 1} , \frac{2}{g_{1} + 1} , …, \frac{g_{1}}{g_{1} + 1} ,

the putative members of the gap between i_{1} and i_{2} by

1 + \frac{1}{g_{2} + 1} , 1 + \frac{2}{g_{2} + 1} , …, 1 + \frac{g_{2}}{g_{2} + 1} ,

…

the putative members of the gap between i_{k−1} and i_{k} by

k − 1 + \frac{1}{g_{k} + 1} , k − 1 + \frac{2}{g_{k} + 1} , …, k − 1 + \frac{g_{k}}{g_{k} + 1} ,

and the putative members of the gap between i_{k} and n by

k + \frac{1}{g_{k+1} + 1} , k + \frac{2}{g_{k+1} + 1} , …, k + \frac{g_{k+1}}{g_{k+1} + 1} .

Now if each and every one of the (g_{1} + g_{2} + … + g_{k+1})! permutations of {1, …, k} union the above putative elements, that start with π contains one of the patterns of P, then we know for sure that the set of permutations whose first k entries reduce to π and that obey the gap-conditions imposed by g, and that avoid P, is the empty set, since such permutations do not exist.

Example: If P = {1234, 1243} and π = 12 then g = [0, 0, 2] is a gap vector. Indeed, introducing the putative entries 2 + 1/3 = \frac{7}{3} and 2 + \frac{2}{3} = \frac{8}{3}, we see that all the 2! = 2 members of the set

\{[1, 2, \frac{7}{3}, \frac{8}{3}], [1, 2, \frac{8}{3}, \frac{7}{3}]\}

contain a pattern of P.

Definition: Given a set of patterns P to avoid, and a prefix permutation π = π_{1} … π_{k}, an unfortunate event is a pair [S, p] where S = {1 ≤ r_{1} < … < r_{s} ≤ k} is a subset of {1, …, k}, p = p_{1} … p_{s}p_{s+1} … p_{a} ∈ P, and π_{r_{1}} … π_{r_{s}} reduces to the same permutation of {1, …, s} as p_{1} … p_{s}. In other words the subpermutation of π consisting of π_{r_{1}} … π_{r_{s}} may be the first s entries in an occurrence of a pattern p ∈ P in the examined permutation.

Examples of unfortunate events: If π = 213, and P = {1342, 2134}, then the following are all the unfortunate events.

[{1}, 1342] , [{1}, 2134] , [{2}, 1342] , [{2}, 2134] , [{3}, 1342] , [{3}, 2134] ,

[{1, 2}, 2134] , [{1, 3}, 1342] , [{2, 3}, 1342] , [{1, 2, 3}, 2134] .

Definition of Reversely Deletable

Suppose that you are given a set of pattens P, and a prefix-permutation π = π_{1} … π_{k}, and you have already found a (possibly empty) set of gap vectors, the entry t, 1 ≤ t ≤ k, is called reversely deletable if any unfortunate event [S, p] where t ∈ S, that obeys the gap conditions, logically implies another unfortunate event [S′, p′] where t ∉ S′.

Examples of Reversely deletable

• P = {123}, π = 21. Here G = {}.

1 is reversely deletable. There is only one unfortunate event that 1 participates in, namely [{1}, 123], but any such event entails a 123 pattern σ_{j_{1}}σ_{j_{2}}σ_{j_{3}} where j_{1} = 1 and, of course, σ_{1} < σ_{j_{2}} < σ_{j_{3}}. But this implies that σ_{2} < σ_{j_{2}} < σ_{j_{3}}, since σ_{1} > σ_{2}, hence the unfortunate event [{2}, 123].

• P = {123}, π = 12. Here G = {[0, 0, 1]}, since a permutation that starts with i_{1}i_{2} with i_{1} < i_{2} can’t have i_{2} < n, so i_{2} = n.

2 is reversely deletable. There is no unfortunate event that i_{2} = n can participate in, so it is true by default.

Scenarios

Every unfortunate event can occur with many scenarios. Consider an unfortunate event [S, p]. Let s be the number of elements of S and let a be the length of p. Let

S = {1 ≤ r_{1} < r_{2} < … < r_{s} ≤ k} , p = p_{1} … p_{s}p_{s+1} … p_{a} .

We know that the reduction of i_{π_{r_{1}}} i_{π_{r_{2}}} … i_{π_{rs}} is the same as the reduction of p_{1}, …, p_{s}. Not only that, in any actual permutation where that unfortunate event takes place, and if a_{1}, …, a_{s} are the actual entries that correspond to the p_{1}, …, p_{s} respectively then we have:

i_{π_{r_{1}}} = a_{1} , …, i_{π_{rs}} = a_{s} .

Imagine that there are k men and a women. Let’s declare that Mr. π_{r_{j}} married Ms. p_{j}, for j = 1 … s. Note that for each married couple, the husband and wife have exactly the same height.

Let J_{1}, …, J_{s} be the sorted list of the married gentlemen π_{r_{1}} … π_{r_{s}}. Let K_{1}, …, K_{s} be the sorted list of the married ladies p_{1}, …, p_{s}. We know that

Ms. K_{1} has the exact same height as Mr. J_{1},

Ms. K_{2} has the exact same height as Mr. J_{2},

…

Ms. K_{s} has the exact same height as Mr. J_{s}.

How can the heights of the remaining women (who are unmarried) be in relation to the heights of the k men (where we agree that the height of Mr. i is i, for 1 ≤ i ≤ k). All the women shorter than Ms. K_{1} (whose height is J_{1}), must be shorter than Mr. J_{1}. But there are usually lots of options on how they compare, in height, with Mr.1, Mr. 2, …, Mr. J_{1} − 1.

Consider the open intervals (0, 1), (1, 2), …, (J_{1} − 1, J_{1}). Now all the K_{1} − 1 shortest women may be shorter than Mr. 1, in which case they would all be in the interval (0, 1), and we would rename them

\frac{1}{K_{1}} , \frac{2}{K_{1}} , \frac{K_{1} − 1}{K_{1}} ,

or-for example-they can all be taller than Mr. 1 but shorter than Mr. 2, in which case we would rename them

1 + \frac{1}{K_{1}} , 1 + \frac{2}{K_{1}} , 1 + \frac{K_{1} − 1}{K_{1}} ,

or the two shortest women can be shorter than Mr. 1, the next two, taller than Mr. 1 but shorter than Mr. 2, and the remaining K_{1} − 5 women could be taller than Mr. J_{1} − 1 but of course shorter than Mr. J_{1}, in which case we would rename the shortest K_{1} − 1 women:

\frac{1}{3} , \frac{2}{3} , \frac{4}{3} , \frac{5}{3} , J_{1} − 1 + \frac{1}{K_{1} − 4} , …, J_{1} − 1 + \frac{K_{1} − 5}{K_{1} − 4} ,

and so on and so forth.

Next we have to take care of Ms. K_{1} + 1, Ms. K_{1} + 2, …, Ms. K_{2} − 1. We know that Ms. K_{2} is exactly of the same height as Mr. J_{2}, and hence is renamed J_{2}. Once again we look at all the possible relative placements, and rename them accordingly. We do this for each and every bunch of single women whose heights are between two married women of “consecutive” height, and thereby get all the scenarios. Each scenario is an increasing list of positive rational numbers of length a, where the K_{1} entry equals J_{1}, the K_{2} entry equals J_{2}, …, the K_{s} entry equals J_{s}. The remaining entries are fractions describing the relative heights with respect to the men’s heights.

Examples of Scenarios Let

π = 4213 , P = {p = 745183269} .

Consider the unfortunate event: [{1, 3}, p]. This means that Mr. 4 married Ms. 7, and Mr. 1 married Ms. 4. Equivalently, Ms. 4 married Mr. 1 and Ms. 7 married Mr. 4. So each and every corresponding scenario must fit the template

[ , , , 1, , , 4, , ] .

We have to figure out all the scenarios compatible with the above template. Regarding Ms. 1, Ms. 2, and Ms. 3, they must be in the interval (0, 1), (since the shortest married woman, Ms. 4 married Mr. 1), so we have

[\frac{1}{4}, \frac{2}{4}, \frac{3}{4}, 1, , , 4, , ] .

Now, regarding Ms. 5 and Ms. 6, they must be taller than Mr. 1, and shorter than Mr. 4, but otherwise may be in any relation with respect to Mr. 2 and Mr. 3.

If they are both shorter than Mr. 2, then we would have the (partial) scenario:

[\frac{1}{4}, \frac{2}{4}, \frac{3}{4}, 1, \frac{4}{3}, \frac{5}{3}, 4, , ] .

If Ms. 5 is shorter than Mr. 2, but Ms. 6 is between Mr. 2 and Mr. 3, then we would have the (partial) scenario:

[\frac{1}{4}, \frac{2}{4}, \frac{3}{4}, 1, \frac{3}{2}, \frac{5}{2}, 4, , ] .

If Ms. 5 is shorter than Mr. 2, but Ms. 6 is between Mr. 3 and Mr. 4 then we would have the (partial) scenario:

[\frac{1}{4}, \frac{2}{4}, \frac{3}{4}, 1, \frac{3}{2}, \frac{7}{2}, 4, , ] .

If Ms. 5 is taller than Mr. 2 but shorter than Mr. 3, and Ms. 6 is between Mr. 3 and Mr. 4 then we would have the (partial) scenario:

[\frac{1}{4}, \frac{2}{4}, \frac{3}{4}, 1, \frac{5}{2}, \frac{7}{2}, 4, , ] ,

and so on.

We still have to place Ms. 8 and Ms. 9, but they are forced (in this example) to be 4 + \frac{1}{3} and 4 + \frac{2}{3}, so the very last partial scenario (right above) is completed into the (complete) scenario

[\frac{1}{4}, \frac{2}{4}, \frac{3}{4}, 1, \frac{5}{2}, \frac{7}{2}, 4, \frac{13}{3}, \frac{14}{3}] .

Weeding-out Scenarios Due to Gap-Vectors

Of course, if there is (are) non-trivial gap-vector(s) then many scenarios can be ruled out, since we know that they give the empty set.

Logical Proof of Reversely-Deletable

Given a set of patterns P to avoid, and a prefix permutation π = π_{1} … π_{k}, to prove that t is reversely deletable, we look at all unfortunate events [S, p] (t ∈ S, p ∈ P) it can conceivably participate in. For each of these unfortunate events, we examine all the scenarios (as above), and implement each scenario by replacing the elements of p by their new “names”. Let s be the number of elements of S. We now delete the entry π_{t} and see whether the resulting “permutation” (with some of them fractions) of length (k − 1) + a − s contains one of the patterns of P. If that happens for each and every scenario, and for each and every unfortunate event (containing t), then we can rest assured that t is indeed reversely deletable.

More precisely, Given a set of patterns P, and a prefix permutation π = π_{1} … π_{k}, then t (1 ≤ t ≤ k) is reversely deletable if for every unfortunate event [S, p_{1} … p_{s} … p_{a}], with p ∈ P and t ∈ S, and for each and every one of its scenarios (recall that a scenario is a list of length a): [x[1], …, x[a]], the sequence obtained by replacing p_{s+1} by x[p_{s+1}], p_{s+2} by x[p_{s+2}], …, p_{a} by x[p_{a}], in

[π_{1}, …, π_{t−1}, π_{t+1}, … π_{k}, p_{s+1}, …, p_{a}]

contains one of the patterns of P.

Looking For a Scheme

We first decide the maximum depth that we are willing to put up with, and the maximum size of the gap vectors. We start with the empty prefix permutation. Whenever we encounter a new prefix permutation, π, (as a child of an already existing prefix permutation), we first try to find a set of gap vectors up to prescribed size. Then we look for the set of reversely deletable elements, T. If T is empty, then we have to consider it an internal vertex, and introduce all its children. If we have reached the inputted depth and still encounter prefix permutations without reversely deletable elements, we terminate with FAIL. Of course, we can try again with larger parameters, but, sometimes there is no enumeration scheme of our kind, of any depth.

The Maple Package VATTER

Everything here is implemented in the Maple package VATTER that can be downloaded from the webpage of this article:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/vatter.html ,

that also contains lots of input and output for the main procedure SipurF, that systematically tries to find all the enumeration schemes, of the inputted depth, for families of set of patterns specified by the sizes of its constituent permutations. Type ezra(); for general help, and ezra(SipurF); for help with the latter.

References

[V] Vince Vatter, Enumeration Schemes for Restricted Permutations, Combinatorics, Probability, Computing, to appear.

Available from Vatter’s website and from http://arxiv.org/abs/math.CO/0510044.

[Z1] Doron Zeilberger, Enumeration Schemes, and More Importantly, Their Automatic Generation, Annals of Combinatorics 2, 185-195 (1998). Also available from Zeilberger’s website.

[Z2] Doron Zeilberger, Automatic CounTilings, The personal Journal of Ekhad and Zeilberger,

2006. http://www.math.rutgers.edu/~zeilberg/pj.html .