%wilf.tex: ``Enumeration Schemes And (More Importantly)
%Their Automatic Generation ''
%a Plain TeX file of an article D. Zeilberger
%begin macros
\def\L{{\cal L}}
\def\P{{\cal P}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\lheading#1{\bigbreak \noindent {\bf#1}
}
\parindent=0pt
\overfullrule=0in
%end macros
\bf
\centerline
{ENUMERATION SCHEMES AND, MORE IMPORTANTLY, THEIR AUTOMATIC GENERATION}
\bigskip
\centerline{ {\it Doron ZEILBERGER}\footnote{$^1$}
{\eightrm \raggedright
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA.
%\break
{\eighttt zeilberg@math.temple.edu} \hfill \break
{\eighttt http://www.math.temple.edu/\Tilde zeilberg .}
May 13, 1998. Supported in part by the NSF.
}
}
\rm
{\bf Towards the Virtual Combinatorialist}
It is way too soon to teach our computers how to become
full-fledged {\it humans}. It is even premature to teach them
how to become {\it mathematicians}, it is even unwise, at present, to teach
them how to become {\it 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 {\it feasibility}, and
{\it 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 {\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 {\it 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.
{\bf Accompanying Software}
In a sense, this article is a user's manual for
the Maple package {\tt WILF}, available from
my homepage {\tt http://www.math.temple.edu/\Tilde zeilberg}
(click on {\tt Maple packages and programs}, and then download
{\tt WILF}). The empirical version of the rigorous
{\tt WILF} is {\tt HERB}, also available there.
{\bf 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:=\vert A_n\vert$,
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, \dots , n\}$,
then $B_n$ may be taken as the set of words of length
$n$ over the alphabet $\{1,2, \dots , 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 {\it 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$.
But a much better approach would be to find a
{\it 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}, \dots $, and easy-to-count
sets, getting a {\it recurrence formula}. Going back to the
permutation example, Levi Ben Gerson ([L]) proved the structure
theorem $A_n \equiv \{1,2, \dots , n\} \times A_{n-1}$, from which
he deduced the {\it recurrence} $a_n=n a_{n-1}$, enabling a
polynomial-(in fact linear-) time algorithm for computing
$a_i$, for $1 \leq i \leq n$.
Alas, this is not always easy, and for many enumeration sequences,
e.g. the number of self-avoiding walks, may well be
{\it impossible}, and who knows, perhaps one day even
{\it provably impossible}.
It is conceivable, however, that a combinatorial family
$A(n)$, does not possess a recursive structure by itself, but by
{\it refining it}, using a suitable parameter, one can partition
$A(n)$ into the disjoint union:
$$
A(n)= \bigcup_{i=1}^{n} B(n,i) \quad,
$$
and try and find a {\it structure theorem} for the two-parameter
family $B(n,i)$. This will imply a recurrence for the
cardinalities $b(n,i):=\vert B(n,i) \vert$, that would enable
a fast algorithm for $a(n)=\sum_{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)= \bigcup_{j=1}^{i-1} C_1(n,i,j) \cup \bigcup_{j=i+1}^{n}
C_2(n,i,j) \quad,
$$
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
$mi$), 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 $\sigma_a$ and the ``$3$''
would be a certain $\sigma_b$, with $2 0$.
A {\it prefix scheme} can be defined independently of sets
of forbidden patterns $\P$ as follows.
{\bf The Formal Definition of Prefix Scheme}
{\bf Definition}: A {\bf 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 $\phi$. $Expa$ and $Redu$ are
disjoint.
(iii) $A$ is a table assigning to each member $\sigma=\sigma_1 \dots \sigma_k$
of $Redu$, a place $A[\sigma]$ in $\sigma$, i.e. an integer
$i$ between $1$ and $k$.
(iv) $B$ is a table assigning to each permutation
$\sigma=\sigma_1 \dots \sigma_k$ of $Expa$, its $k+1$ refinements.
(v) $C$ is a table that assigns to each member
$\sigma=\sigma_1 \dots \sigma_k$ of
$Redu\cup Expa$ a certain set $J(\sigma)$, which is a (possibly empty)
subset of $\{0,1, 2, \dots , k \} $.
(vi) For each $\sigma \in Expa$, each member $B[\sigma]$ must belong
to $Expa \cup Redu$.
For example, the following $[Redu, Expa,A,B,C]$
is a prefix scheme: $Redu=\{12,21\}$, $Expa=\{\phi,1\}$,
$A[12]=1, A[21]=1$, $B[\phi]=\{1\}, B[1]=\{12,21\}$,
$C[12]=\{2\}, C[21]=C[1]=C[\phi]=\emptyset$.
We are now ready to interface the abstract notion of {\it prefix
scheme} to that of {\it forbidden patterns}.
{\bf Another Important Definition}:
A {\bf Prefix Scheme} $[Redu, Expa, A,B,C]$ is an {\bf Enumeration
Scheme} for a set of forbidden patterns $\P$, if the following
conditions hold:
(i) For every $\sigma \in Redu$, let $\sigma'$ be the reduction of
the permutation obtained from $\sigma$ by deleting the entry at the
place specified by $A[\sigma]$. The following property holds:
If you take any permutation $\pi$ that avoids the patterns
in $\P$, and that has a prefix that reduces to $\sigma'$, and
insert a new entry right before the $(A[\sigma]+1)^{th}$ place
of $\pi$, in such a way that the new permutation has a prefix
that reduces to $\sigma$, then that new permutation also avoids
the patterns of $\P$. In other words, the insertion is always
safe.
(ii) Suppose that a permutation $\pi$
of $\{1,2, \dots, n \}$, avoids the patterns of $\P$,
and has a prefix that reduces to one of the permutations
$\sigma=\sigma_1 \dots \sigma_k$ of $Expa \cup Redu$, and
the first $k$ entries of $\pi$ are
$i_{\sigma_1} i_{\sigma_2} \dots i_{\sigma_k}$, where, of course,
$1 \leq i_1< i_2 < \dots < i_k \leq n$. Then
if $0 \in C[\sigma]$, we MUST have $i_1=1$, and if
$k \in C[\sigma]$, we MUST have $i_k=n$, and for any other
member $j$ of $C[\sigma]$, we MUST have $i_j=i_{j+1}$.
{\bf 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 $\sigma=\sigma_1 \dots \sigma_k \in Expa$,
let $\sigma^{(j)}$ ($1 \leq j \leq k+1$), be that member of
$B[\sigma]$ that ends with $j$. We have, for $1 \leq i_1 < \dots < i_k \leq n$
$$
a_\sigma(n;\P;i_1, \dots , i_k)=
\sum_{j=1}^{k+1}
\sum_{r=i_{j-1}+1}^{i_j-1}
a_{\sigma^{(j)}}(n;\P;i_1, \dots, i_{j-1}, r, i_j,\dots , i_k) \quad,
$$
where $i_0=0$ and $i_{k+1}=n+1$.
If $\sigma=\sigma_1 \dots \sigma_k$ is in $Redu$,
let $A[\sigma]=r$.
If $C[\sigma]=\emptyset$, then
$$
a_\sigma(n;\P;i_1, \dots , i_k)=
a_{\sigma_{(r)}}(n-1;\P;i_1, \dots , i_{r-1}, i_{r+1}-1, \dots , i_k-1)
\quad ,
\eqno(Miklos)
$$
where $\sigma_{(r)}$ is the permutation obtained
by reducing the permutation obtained from
$\sigma$ by deleting $\sigma_r$.
If $J:=C[\sigma] \neq \emptyset$ then $(Miklos)$ holds
whenever $(i_1, \dots, i_k)$ ``obeys $J$'', i.e.
whenever $i_j=i_{j+1}$ for all $j\in J$
(recall that $i_0=1$, $i_{k+1}=n$).
Otherwise $a_\sigma(n;\P;i_1, \dots , i_k)=\emptyset$.
Since the sets $Redu$ and $Expa$ are finite, the enumeration
scheme is well-defined.
{\bf 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 {\it 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 $\phi$ as belonging to
$Expa$. Its only refinement is $1$. Unless
$\P=\emptyset$, $1$ would also belong to $Expa$. Its
refinements are $12$ and $21$. We examine each prefix
permutation $\sigma$, in turn, and see whether it has
a non-empty $J:=C[\sigma]$ (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 {\it 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 $\sigma$ becomes a member of $Redu$,
and the lucky place, that made it a member is recorded as
$A[\sigma]$. If there are no such places, we reluctantly
put $\sigma$ in $Expa$, and find its refinements, that
we store as $B[\sigma]$. 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 \cup Redu$.
{\bf Important Remark:} All the above deductions are made
completely automatically by the computer. So we have
(a very primitive) `Artificial Intelligence'.
{\bf Using the Maple package} {\tt WILF}
The procedure in the package {\tt WILF}, that looks for
Schemes for a set of patterns, is {\tt Scheme}.
The syntax is: ``Scheme(Set\_Of\_Patterns,Maximal\_Depth)''.
For example, to get a scheme for $\P=\{123,132\}$, type:
``{\tt 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 {\tt sch}), to find
the number of permutations on $n$ objects avoiding the
patterns $\P$, you do ``$Miklos(n,sch);$''.
For example ``{\tt Miklos(3,sch);}'' should yield
{\tt 4}. To get the
first $L$ terms of the sequence $a(n; \P)$ (after
$sch:=Scheme(\P;Depth)$ was successful for some $Depth$),
do ``{\tt SchemeSequence(sch,L);}''. The
package {\tt WILF} could also try to guess (empirically,
but perhaps rigorizably), a linear recurrence with
polynomial coefficients. This procedure is called
{\tt SchemeRecurrence}. The reader should look up the on-line help.
{\tt SchemeF} does what Scheme does, but more generally,
by trying {\tt Scheme} on all on the images of $\P$ under
the dihedral group consisting of inverse, and reverse.
This paper's website
{\tt http://www.math.temple.edu/\Tilde zeilberg/WILF.html}
has numerous sample input and output files.
{\bf The Maple package } {\tt HERB}
This is the non-rigorous counterpart of {\tt WILF}.
There a scheme is found empirically by checking
$(Julian)$ for small $n$, and extrapolating.
It was written before the rigorous {\tt WILF}, and
helped a lot in developing the latter.
{\bf Future Directions}
Prefix Schemes are equivalent to Suffix Schemes, but it should
be possible to have {\it mixed schemes}. Also one may be even
more creative in partitioning $A_\sigma$. Hopefully,
a more general notion of {\it scheme} would be more
successful. Also, it should be possible to
{\it empirically} guess {\it generating functions}
(or perhaps, {\it redundant generating functions} (in the
sense of MacMahon)), for the $A_\sigma$,
in $Redu \cup Expa$, which, once guessed, are rigorously
provable. This, in particular, would entail a
{\it constant-term expression} for $A(n; \P)$, which,
by using the WZ method, should lead to a {\it rigorous}
derivation of the recurrence guessed by procedure
{\tt SchemeRecurrence} in {\tt WILF}.
{\bf REFERENCES}
[K] Donald E. Knuth, ``{\it The Art of Computer Programming}'',
vol.3, Addison-Wesley, Reading, MA, 1973. Second Edition 1997.
[L] Levi Ben Gerson, ``{\it Sefer Ma'asei Khosev}'', 1321, Orange, France.
[Extant printed version in: Gerson Lange, Frankfurt: Louis Golde, 1909.]
[We] Julian West, {\it Generating trees and Catalan and Schr\"oder numbers},
Discrete Mathematics {\bf 146}(1995), 247-262.
[Wi] Herbert S. Wilf, {\it What is an Answer?}, Amer. Math. Monthly
{\bf 89}(1982), 289-292.
\bye