%vatter.tex:
%%a Plain TeX file by Doron Zeilberger (9 pages)
%''On Vince Vatter's Brilliant Extension of Doron
%Zeilberger's Enumeration Schemes for Herb Wilf's Classes
%Permutations''
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\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\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\def\Tilde{\char126\relax}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm \ifodd\pageno \RightHead \else \LeftHead \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
On Vince Vatter's Brilliant Extension of
}
\centerline
{ Doron Zeilberger's Enumeration Schemes for
Herb Wilf's Classes
}
\rm
\bigskip
\centerline{ {\it
Doron
ZEILBERGER}\footnote{$^1$}
{\eightrm \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg} .
First version: Dec. 29, 2006.
This version: March 28, 2007 [incorporating
Lara Pudwell's and Vince Vatter's referee reports available from
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/
mamarimhtml/vatter.html}] .
Accompanied by Maple package {\eighttt VATTER}
downloadable from Zeilberger's website.
Supported in part by the NSF.
}
}
{\bf Retail vs. Wholesale Enumeration}
An enumerative {\it retailer} studies {\it one problem at
a time}. On the other hand, an enumerative {\it wholesaler}
studies a {\it family of problems}, and tries to
design {\it algorithms} that can be {\it implemented}
to solve lots and lots of problems from that family.
{\bf Doron Zeilberger's Original Enumeration Schemes}
In [Z1] I tackled the problem of enumerating
{\it Wilf classes}, i.e. finding ``schemes'' for enumerating
sets of {\it permutations} avoiding a given set of
{\it patterns}. Alas, the success rate was rather
disappointing.
{\bf Vince Vatter's Brilliant Extension}
In [V], my brilliant {\it disciple}, Vince Vatter, introduced a
{\it far-reaching} extension: gap vectors!
This made the success rate much higher!
{\bf 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 {\tt WILF}.
To check the `logical' program, I also
wrote an empirical program, called {\tt HERB}.
The Maple package {\tt HERB} found enumeration schemes
by testing them for permutations of size $n \leq N_0$,
where $N_0$ was some positive integer chosen by
the user. But to {\it rigorously} prove
the validity of the candidate enumeration schemes we still need
the `logical' program {\tt WILF}, since the
{\it empirical} program, {\tt HERB},
is {\it just that}, empirical! {\bf OR IS IT?}.
{\bf 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 {\it kvetching} that a recent paper of mine
`Automatic CounTilings'[Z2], was stupidly and
narrow-mindedly rejected by Journal of Combinatorial
Theory-Series A, and my appeal, to Advisory Board member
Mireille Bousquet-M\'elou, to reconsider, was unsuccessful.
One of the things that the referee, and apparently
also Bousquet-M\'elou, 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 \theta = 2\cos^2 \theta -1$) and I verified it for
$\theta=0, \pi/4, \pi/2$. Since
both sides are Laurent polynomials in $e^{2i \theta}$
of degree $1$ and low-degree
$-1$, this {\it 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\'elou)
too much, since I, myself, committed the same stupidity,
by not realizing that my `empirical' Maple package {\tt 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 \leq N_0$,
proves its validity in general.
Furthermore, the same holds for his more general version of
enumeration schemes, that feature {\it gap vectors}.
That was the approach taken in his own Maple implementation,
{\tt WILFPLUS}, described in [V].
{\bf OK, Empirical Proofs Can (Often) Be Made Rigorous,
But Is It the Most Efficient Way?}
But the ``$N_0$ approach'' is, like everything else,
{\it 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 \theta = (2\cos^2 \theta -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.
{\bf A ``Logical'' Approach to Vatter's Gapped Enumeration
Schemes}
The purpose of the present article, implemented in the
Maple package {\tt VATTER}, is to adapt the ``logical''
approach of [Z1], as implemented in the original Maple
package {\tt WILF}, to Vatter's gapped-extension of
enumeration schemes. It appears that {\tt VATTER} runs considerably
faster than Vatter's {\tt WILFPLUS}.
{\bf Definition, Examples, Definition, Examples,
Definition, Examples, $\dots$}
{\bf Definition}: The {\it 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$, $\dots$,
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 \leq i \leq k$.
{\it Examples of reduction}: The reduction of $6283$ is
$3142$. The reduction of $\pi \gamma e \phi$ is
$4132$.
{\bf Definition}: The {\it Children} of a permutation
$\pi$ of $\{1, \dots, k\}$ are all the $k+1$ permutations
of $\{1, \dots, k+1\}$
for whom the permutation obtained by chopping the
last entry reduces to $\pi$.
{\it Examples of Children}: The set of children of $132$ is
$\{ 2431 \, , \, 1432 \, , \, 1423 \, , \, 1324 \, \}$ .
{\bf Definition}: A {\it VZ-triple} is a triple
$[\pi,G,T]$ where $\pi$ is a permutation of
$\{1, \dots, k\}$ for some non-negative 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, \dots , k\}$.
{\it Examples of VZ-triples} :
$$
[ [\,\,], \{\}, \{\}] \quad , \quad
[ 132, \{\}, \{\}] \quad , \quad
[ 132, \{[0,2,1,0],[1,1,0,1]\}, \{1,3 \}] \quad .
$$
{\bf Definition:} Let $V$ be a {\it finite} set of VZ-triples,
and let $P$ be the set of first components of its
triples.
$V$ is an {\it abstract VZ- enumeration scheme} if
the following conditions hold:
{\bf 1.} If $[\pi,G,T] \in V$ and $T=\{\}$ then all the
children of $\pi$ are in $P$.
{\bf 2.} If $[\pi,G,T] \in V$ and $T \neq \{\}$ then $T$
has at least one member, let's call it $t$, such that
the reduction of the permutation obtained from $\pi$ by deleting its $t^{th}$
entry belongs to $P$.
{\it An Example of an abstract enumeration scheme}:
$$
\{ \,\, [[\,\,],\{\},\{ \}] \quad , \quad
[\, 1, \, \{\},\{\}] \quad , \quad
[\, 12 \, , \, \{[0,0,1]\},\{2\}] \quad , \quad
[\, 21 \, ,\, \{\},\{1\}] \,\, \} \quad .
$$
{\bf Definition} Let $\{S(n), \, n \geq 0 \, \}$ be a sequence of sets,
where $S(n)$ is a set of permutations of $\{1, \dots , n\}$.
For any permutation $\pi=\pi_1 \dots \pi_k$ , and any
increasing $k$-tuple of integers $(i_1, \dots, i_k)$, where
$1 \leq i_1 < i_2 < \dots < i_k \leq n$, let
$S(n)[\pi](i_1, \dots, i_k)$ be the set of members of
$S(n)$ whose first $k$ entries are (in that order)
$i_{\pi_1} \dots i_{\pi_k}$ (and hence their prefix
of length $k$ reduces to $\pi$ and consists of
$\{i_1, \dots, i_k \}$).
An {\it abstract} enumeration scheme $V$ becomes
a {\bf concrete} enumeration scheme for $\{S(n)\}$ if
{\bf 1.}
For {\it any} member of $V$,
$[\pi=\pi_1 \dots \pi_k \, ,\, G \, ,\, T \,]$,
and for {\it any} $g \in G$,
the following holds.
If
$$
i_1-1 \geq g_1 \quad AND \quad
i_2-i_1-1 \geq g_2 \quad AND \quad \dots \quad AND \quad
i_{k}-i_{k-1}-1 \geq g_k \quad AND \quad
n+1-i_k-1 \geq g_{k+1} \quad ,
\eqno(GapConditions(g))
$$
then $S(n)[\pi](i_1, \dots, i_k)$ is the empty set.
{\bf 2.}
For any member of $V$,
$[\pi=\pi_1 \dots \pi_k \, ,\, G \, ,\, T \,]$, the
following holds.
For every element $t \in T$, and every $n \geq k$,
and every increasing sequence of integers
$1 \leq i_1 < i_2 < \dots < i_k \leq n$
that {\bf do not} obey any of $(GapConditions(g))$ ($g \in G$),
$$
\vert S(n)[\pi](i_1, \dots, i_k) \vert=
\vert S(n)[\pi'](i'_1, \dots, i'_{k-1}) \vert \quad.
$$
where $\pi'$ is the reduction of the permutation of length $k-1$
obtained by deleting $\pi_t$ from $\pi$, and
$(i'_1, \dots, i'_{k-1})$ is the reduction of
of the vector obtained from $(i_1, \dots, i_k)$ by deleting
$i_{\pi_t}$.
{\bf Remark:} If $V$ is a concrete enumeration scheme for
$\{S(n)\}$, then we have a {\bf polynomial-time} algorithm for
enumerating the sequence $s_n:=\vert S(n) \vert$.
We need to compute for {\it each}
$[\pi=\pi_1, \dots, \pi_k,G,T] \in V$ and
for {\it each} sequence $1 \leq i_1 < \dots < i_k \leq n$
(there are ${{n} \choose {k}}=O(n^k)$ such sequences of course)
the number of elements of $S(n)[\pi](i_1, \dots , i_k)$.
If at least one of the $GapConditions(g), (g \in G)$ is satisfied, we know
immediately that it is $0$.
If $T \neq \{\}$ and $t \in T $ is such
that the reduction of $\pi_1, \dots, \pi_{t-1} \pi_{t+1}, \dots \pi_k$
belongs to $P$, then it is
$\vert S(n)[\pi'](i'_1, \dots, i'_{k-1}) \vert$.
Finally if $T=\{\}$, we express
this quantity in terms of the children of the permutation and
the ``children'' of $(i_1, \dots, i_k)$. By the definition
of ``abstract enumeration scheme'', this will give an effective
way of computing all the $\vert S(n)[\pi][i_1, \dots , i_k] \vert $,
and in particular, our object of desire, $\vert S(n)[\,\,][\,\,]\vert$,
which is $\vert S(n) \vert$ of course.
{\bf Restricted Permutations}
{\bf Definition}: A {\it pattern} of length $a$
is a permutation $p_1 \dots p_a$ of $\{1,2, \dots , a \}$.
(used in the context below).
{\bf Definition}: A permutation $\sigma=\sigma_1 \dots \sigma_n$
{\it contains} the pattern $p=p_1 \dots p_a$, if
there exist $1 \leq j_1 < j_2 < \dots < j_a \leq n$ such that
$\sigma_{j_1}\sigma_{j_2} \dots \sigma_{j_a}$ reduces to $p$.
{\it 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$.
{\bf Definition}: A permutation $\sigma=\sigma_1 \dots \sigma_n$
{\it avoids} the pattern $p=p_1 \dots p_a$, if
it does {\bf not} contain it.
{\it Example of avoiding a pattern:} The permutation
$45321$ avoids the pattern $132$, since none of the ${{5} \choose {3}}$
subsequences of $45321$, of length $3$, which are:
$$
453,452,451,432,431,421,532,531,521,321 \quad ,
$$
reduce to $132$. (They reduce to
$231,231,231,321,321,321,321,321,321,321$ respectively).
{\bf Definition}: A permutation $\sigma=\sigma_1 \dots \sigma_n$
{\it avoids} the set of patterns $\P$, if
it avoids {\it every} pattern $p \in \P$.
{\it Example of avoiding a set of patterns:} The permutation
$45321$ avoids the
set of patterns $\P=\{123,132,312\}$,
since none of the ${{5} \choose {3}}$
subsequences of $45321$, to wit:
$$
453,452,451,432,431,421,532,531,521,321 \quad
$$
reduces to one of the members of $\P$.
Given {\it any} set of patterns $\P$,
our goal is to try and find a {\bf concrete enumeration scheme}
for the sequence of sets of permutations $\{S(n)\}$ where
$S(n)$ is the set of permutations of $\{1,2, \dots , n\}$ that
avoid all the patterns of $\P$.
{\bf How to Find Gap Vectors?}
Given a {\it prefix-permutation}, $\pi=\pi_1 \dots \pi_k$, and a vector
$g=[g_1, \dots , g_{k+1}]$, we want to see whether
$(GapConditions(g))$ {\it guarantee} that the corresponding
set is empty. One way to do it, is to look at a
{\it putative} permutation obeying the gap conditions.
If all the conditions (for $g$) hold it means that
there is a ``gap'' of size $g_1$ {\it between} $0$ and $i_1$,
{\it and} a ``gap'' of size $g_2$ between $i_1$ and $i_2$, $\dots$,
{\it and} a gap of size $g_{k+1}$ between $i_k$ and $n$. Since everything
depends on the {\it reduction} we can {\it rename}
$i_1$ to be $1$, $i_2$ to be $2$, $\dots$, $i_k$ to be $k$
{\bf and }
the putative members of the gap between $0$ and $i_1$
by
$$
{{1} \over {g_1+1}} \quad,\quad
{{2} \over {g_1+1}} \quad, \quad \dots \quad , \quad
{{g_1} \over {g_1+1}} \quad,
$$
the putative members of the gap between $i_1$ and $i_2$ by
$$
1+{{1} \over {g_2+1}} \quad, \quad
1+{{2} \over {g_2+1}} \quad, \quad \dots \quad , \quad
1+{{g_2} \over {g_2+1}} \quad,
$$
$$
\dots
$$
the putative members of the gap between $i_{k-1}$ and $i_k$ by
$$
k-1+{{1} \over {g_k+1}} \quad, \quad
k-1+{{2} \over {g_k+1}} \quad, \quad \dots \quad, \quad
k-1+{{g_k} \over {g_k+1}} \quad,
$$
and the putative members of the gap between $i_{k}$ and $n$ by
$$
k+{{1} \over {g_{k+1}+1}} \quad, \quad
k+{{2} \over {g_{k+1}+1}} \quad, \quad \dots \quad , \quad
k+{{g_{k+1}} \over {g_{k+1}+1}} \quad .
$$
Now if {\it each and every}
one of the $(g_1+g_2+\dots+g_{k+1})!$ permutations of
$\{1,\dots,k\}$ union the above putative elements, that
start with $\pi$
{\it contains one of the patterns of $\P$}, then we know {\bf for sure}
that the set of permutations whose first $k$ entries reduce to $\pi$ and
that obey the gap-conditions imposed by $g$,
and that avoid $\P$, is the empty set, since such permutations
{\it do not exist}.
{\it Example}: If $\P=\{1234,1243\}$ and $\pi=12$ then
$g=[0,0,2]$ is a gap vector. Indeed, introducing the
putative entries $2+1/3={{7} \over {3}}$ and
$2+{{2} \over {3}}={{8} \over {3}}$, we see that
{\it all} the $2!=2$ members
of the set
$$
\{[1,2,{{7} \over {3}},{{8} \over {3}}],
[1,2,{{8} \over {3}},{{7} \over {3}}]\}
$$
contain a pattern of $\P$.
{\bf Definition:} Given a set of patterns $\P$ to avoid,
and a prefix permutation $\pi=\pi_1 \dots \pi_k$,
an {\it unfortunate event} is a pair $[S,p]$ where
$S=\{1\leq r_1< \dots \sigma_2$,
hence the unfortunate event $[\{2\},123]$.
$\bullet$ $\P=\{123\}$, $\pi=12$. Here $G=\{[0,0,1]\}$,
since a permutation that starts with $i_1 i_2$ with
$i_1