%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-1)[\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-1)[\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 <r_s \leq k\}$ 
is a subset of $\{1,\dots, k\}$, 
$p=p_1 \dots p_s p_{s+1} \dots p_a \in \P$, and
$\pi_{r_1} \dots \pi_{r_s}$ reduces to the same permutation
of $\{1, \dots, s\}$ as $p_1 \dots p_s$.
In other words the subpermutation of $\pi$ consisting
of $\pi_{r_1} \dots \pi_{r_s}$ may be the first
$s$ entries in an occurrence of a pattern $p \in \P$
in the examined permutation.

{\it Examples of  unfortunate events}:
If $\pi=213$, and $\P=\{1342, 2134\}$,
then the following are all the unfortunate events.
$$
[\{1\}, 1342] \quad , \quad [\{1\}, 2134] \quad , \quad
[\{2\}, 1342] \quad , \quad [\{2\}, 2134]\quad , \quad
[\{3\}, 1342] \quad , \quad [\{3\}, 2134]\quad ,
$$
$$
[\{1,2\}, 2134] \quad , \quad [\{1,3\}, 1342] \quad , \quad
[\{2,3\}, 1342] \quad , \quad 
[\{1,2,3\}, 2134] \quad  \quad .
$$

{\bf Definition of Reversely Deletable}

Suppose that you are given a set of pattens $\P$, and a prefix-permutation
$\pi=\pi_1 \dots \pi_k$, and you have already found
a (possibly empty) set of gap vectors,
the entry $t$, $1 \leq t \leq k$,
is called {\bf reversely deletable} if any unfortunate event
$[S,p]$ where $t \in S$, that obeys the gap conditions,
{\bf logically implies} another unfortunate event
$[S',p']$ where $t \not \in S'$.

{\bf Examples of Reversely deletable}

$\bullet$ $\P=\{123\}$, $\pi=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 $\sigma_{j_1} \sigma_{j_2} \sigma_{j_3}$ where
$j_1=1$ and, of course, $\sigma_{1} <\sigma_{j_2}<\sigma_{j_3}$.
But this implies that
$\sigma_{2} <\sigma_{j_2}<\sigma_{j_3}$, since $\sigma_1 > \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<i_2$ can't have $i_2<n$, so $i_2=n$.

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


{\bf Scenarios}

Every unfortunate event can occur with many {\it 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 \leq r_1 < r_2 < \dots < r_s \leq k \} \quad , \quad
p=p_1 \dots p_s p_{s+1} \dots p_a \quad .
$$
We know that the reduction of 
$i_{\pi_{r_1}}i_{\pi_{r_2}} \dots i_{\pi_{r_s}}$
is the same as the reduction of $p_1, \dots, p_s$.
Not only that, in any actual permutation where
that unfortunate event takes place,
and if $a_1, \dots , a_s$ are the {\it actual} entries
that correspond to the $p_1, \dots, p_s$ respectively
then we have: 
$$
i_{\pi_{r_1}}=a_1 \quad , \quad \dots \quad , \quad i_{\pi_{r_s}}=a_s
\quad .
$$

Imagine that there are $k$ men and $a$ women.
Let's declare that  Mr. $\pi_{r_j}$ married
Ms. $p_j$, for $j=1 \dots s$. Note
that for each married couple, the husband and wife have
{\bf exactly the same height}.

Let $J_1, \dots, J_s$ be the sorted list of the married
gentlemen $\pi_{r_1} \dots \pi_{r_s}$. Let
$K_1, \dots, K_s$ be the sorted list of the married ladies
$p_1, \dots, 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$,

$\dots$

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 \leq i \leq 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, $\dots$, 
Mr. $J_1-1$.

Consider the {\it open} intervals $(0,1),(1,2), \dots, (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 
$$
{{1} \over {K_1}} \quad , \quad
{{2} \over {K_1}} \quad , \quad
{{K_1-1} \over {K_1}} \quad , 
$$
or-for example-they can all be taller than Mr. 1 but shorter than Mr. 2,
in which case we would rename them
$$
1+{{1} \over {K_1}} \quad , \quad
1+{{2} \over {K_1}} \quad , \quad
1+{{K_1-1} \over {K_1}} \quad , 
$$
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:
$$
{{1} \over {3}} \quad , \quad
{{2} \over {3}} \quad , \quad
{{4} \over {3}} \quad , \quad
{{5} \over {3}} \quad , \quad
J_1-1+{{1} \over {K_1-4}} \quad , \dots, \quad
J_1-1+{{K_1-5} \over {K_1-4}} \quad ,
$$
{\it and so on and so forth}.

Next we have to take care of Ms. $K_1+1$, Ms. $K_1+2$, $\dots$,
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 {\it scenarios}. Each scenario is
an {\it increasing list of positive rational numbers} 
of length $a$, where the $K_1$ entry equals
$J_1$, the $K_2$ entry equals $J_2$, $\dots$, the
$K_s$ entry equals $J_s$. The remaining entries are
fractions describing the relative heights with respect
to the men's heights.

{\it Examples of Scenarios}

Let 
$$
\pi=4213 \quad , \quad \P=\{p=745183269\} \quad .
$$
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
$$
[\quad , \quad , \quad , 1, \quad , \quad , 4, \quad , \quad  ] \quad .
$$
We have to figure out all the scenarios compatible with
the above template. Regarding Ms. 1, Ms. 2, and Ms. 3, they
{\it must} be in the interval $(0,1)$, (since the shortest
married woman, Ms. 4 married Mr. 1), so we have
$$
[{{1} \over {4}} , 
{{2} \over {4}} ,
{{3} \over {4}} , 
1, \quad , \quad , 4, \quad , \quad ] \quad .
$$
Now, regarding Ms. $5$ and Ms. $6$, they must be taller
than Mr. 1, and shorter than Mr. 4, but otherwise
may be in {\it 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:
$$
[{{1} \over {4}} , 
{{2} \over {4}} , 
{{3} \over {4}} , 
1, 
{{4} \over {3}} , 
{{5} \over {3}} , 
4, \quad , \quad ] \quad .
$$
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:
$$
[
{{1} \over {4}} , 
{{2} \over {4}} , 
{{3} \over {4}} , 
1, {{3} \over {2}} , 
{{5} \over {2}} , 4, \quad , \quad ] \quad .
$$
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:
$$
[{{1} \over {4}} , 
{{2} \over {4}} , 
{{3} \over {4}} , 
1,
{{3} \over {2}} , 
{{7} \over {2}} , 4, \quad , \quad ] \quad .
$$
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:
$$
[{{1} \over {4}} , 
{{2} \over {4}} , 
{{3} \over {4}} , 
1, {{5} \over {2}} , 
{{7} \over {2}} , 4, \quad , \quad ] \quad ,
$$
and so on.

We still have to place Ms. 8 and Ms. 9, but they are
{\it forced} (in this example) to be $4+{{1} \over {3}}$ 
and $4+{{2} \over {3}}$,
so  the very last partial scenario (right above) is completed
into the (complete) scenario
$$
[{{1} \over {4}} , 
{{2} \over {4}} , 
{{3} \over {4}} , 
1, {{5} \over {2}} , 
{{7} \over {2}} , 4, {{13} \over {3}}  , {{14} \over {3}} ] \quad .
$$


{\bf 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.

\vfill\eject
{\bf Logical Proof of Reversely-Deletable}

Given a set of patterns $\P$ to avoid,
and a prefix permutation $\pi=\pi_1 \dots \pi_k$,
to prove that $t$ is reversely deletable, we look
at all unfortunate events $[S,p]$ ($t \in S$, $p \in \P$) it can
conceivably participate in. For {\it each} of these unfortunate
events, we examine {\it 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 $\pi_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 {\it for each and every scenario}, and
for {\it 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 $\pi=\pi_1 \dots \pi_{k}$, 
then $t$ ($1 \leq t \leq k$) is reversely deletable if 
for {\it every} unfortunate event $[S,p_1 \dots p_s \dots p_a]$,
with $p \in \P$ and $t \in S$, and for {\it each and every one of 
its scenarios} 
(recall that a scenario is a list of length $a$): $[x[1], \dots , x[a]]$,
the sequence obtained by replacing $p_{s+1}$ by $x[p_{s+1}]$,
$p_{s+2}$ by $x[p_{s+2}]$, $\dots$, $p_a$ by $x[p_a]$, in
$$
[\pi_1, \dots, \pi_{t-1},\pi_{t+1}, \dots \pi_k, p_{s+1},\dots, p_a]
$$
contains one of the patterns of $\P$.

{\bf 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, $\pi$, (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 {\it no} enumeration scheme of our kind, of {\it any}
depth.

{\bf The Maple Package VATTER}

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

{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/mamarimhtml/vatter.html}   ,

that also contains lots of input and output for the main
procedure {\tt 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 {\tt ezra();} for
general help, and {\tt ezra(SipurF);} for help with
the latter.

{\bf References}

[V] Vince Vatter, {\it Enumeration Schemes for Restricted Permutations},
Combinatorics, Probability, Computing, to appear. \hfill\break
Available from  Vatter's 
website and from {\tt http://arxiv.org/abs/math.CO/0510044}.

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

[Z2] Doron Zeilberger, {\it Automatic CounTilings},
The personal Journal of Ekhad and Zeilberger, 2006.
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/pj.html} \quad .

\end