%soli.tex:  In how many ways can you play Stanley Solitaire?
%%a Plain TeX file  Shalosh B. Ekhad and Doron Zeilberger ( pages)

%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\C{{\cal C}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\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
\centerline
{\bf 
In how many ways can you play Stanley Solitaire?
}
\bigskip
\centerline
{\it Shalosh B. EKHAD and Doron ZEILBERGER}
\bigskip
\qquad {\it Dedicated to Algebraic Combinatorics guru, Richard Stanley (b. June 23, 1944) on his forthcoming 80th birthday}

{\bf Preface: Stanley Solitaire: A Game You Can Teach a Five-Year-Old}

It is noneducational to give candy to children unless they learn something from it. Here is a simple educational game that teaches children
the notions of {\it larger} and {\it smaller}, and {\it left} and {\it right}. We named this game {\it Stanley Solitaire} for a reason to be explained later.

You start with an {\it initial position} on a one-dimensional {\bf board}, where some squares have piles of candies (for example M\&Ms) on them.
The left side of the board is fixed, but one can move as far right as one wishes, following the rules.

One such starting position (out of infinitely many) could be
$$
[4,5,0,0,2,0,3,1] \quad,
$$
meaning that the rightmost location has $4$ candies, the second-from-the-right has $5$ candies, the third, fourth, and sixth locations are empty, the fifth has $2$ candies, the seventh has $3$ candies, and the eighth has
one candy.

The player is allowed to eat all the candies, provided that he or she follow one strict rule.

{\it Whenever in two adjacent locations the number of candies in the left location is (strictly) larger than the right location, exchange them, and eat one of the candies of
the larger pile (the one that initially was on the right, and now is to the left)}. 

If the player messes up, they are not allowed to play anymore, so they have a strong motivation
to follow the rules.

In the above example, the legal moves are

$\bullet$ Eat one candy from the second location, and exchange the second and third,  getting to the new position $[4,0,4,0,2,0,3,1]$ \quad .

$\bullet$ Eat one candy from the fifth location, and exchange the fifth and the sixth piles, getting to the new position $[4,5,0,0,0,1,3,1]$ \quad .

$\bullet$ Eat one candy from the seventh location, and exchange the seventh  and eighth piles, getting to the new position $[4,5,0,0,2,0,1,2]$ \quad .

$\bullet$ Eat one candy from the eighth location, and exchange the eighth and the (implied)  ninth pile getting to the new position $[4,5,0,0,2,0,3,0,0]$, but
we delete all rightmost zeroes, so the new position is $[4,5,0,0,2,0,3]$.



More formally, for a position
$$
[a_1, \dots, a_k] \quad,
$$
where we insist that $a_1>0$ and  $a_k>0$, and otherwise $a_i \geq 0$, the legal moves are
For all $1 \leq i <k$, if $a_i>a_{i+1}$ then go to position
$$
[a_1, \dots, a_{i+1}, a_i -1, \dots, a_k] \quad,
$$
and another legal move is to position $[a_1, \dots, a_{k-1},0,  a_k-1]$. Whenever the new position has $0$ either on the left or right, we remove them, keeping the convention that the leftmost and rightmost piles are non-empty.

{\bf A problem you can Explain To a Five-Year-Old}

If you start at a given position, say $[5,4,3,2,1]$, so you can eat $15$ candies as long as you follow the rules, how many ways can you do it?

It turns out (see later) that the number is $292864$.

If the initial position is $[2,1]$, then there are only two ways:

$$
[2,1] \rightarrow [1,1] \rightarrow [1] \rightarrow [] \quad ,
$$
$$
[2,1] \rightarrow [2,0,0] (\,alias \, [2]\,) \rightarrow [1] \rightarrow [] \quad .
$$

While if the starting position is $[2,2,1]$ there are five ways:
$$
[[2, 2, 1], [2, 1, 1], [1, 1, 1], [1, 1], [1], []] \quad,
$$
$$
[[2, 2, 1], [2, 1, 1], [2, 1], [1, 1], [1], []] \quad,
$$
$$
[[2, 2, 1], [2, 1, 1], [2, 1], [2], [1], []] \quad,
$$
$$
[[2, 2, 1], [2, 2], [2, 0, 1], [1, 1], [1], []] \quad,
$$
$$
[[2, 2, 1], [2, 2], [2, 0, 1], [2], [1], []] \quad.
$$

{\bf An Answer you can Explain to a Seven-Year-Old}

Thanks to the seminal work of Richard Stanley [S], and independently, Paul Edeleman, and Curtis Greene [EG] (and presuambly [LSc], but it is over our heads), there is
an extremely easy and elegant {\bf answer}, that only involves addition and multiplication (recall that $a!=1 \cdot 2 \cdots a$)

{\bf A Simply Stated but Surprisingly Hard-To-Prove Theorem} ([S],[EG])

The {\bf exact} number of ways to play Stanley-Solitaire starting with position, 
$$
[a_1, \dots, a_k] \quad,
$$
where $a_1 \geq a_2 \geq \dots \geq a_1 >0$ is
$$
\frac{(a_1+ \dots + a_k)!}{(a_1+k-1)! (a_2+k-2)! \cdots (a_k)!} \cdot \prod_{1 \leq i < j \leq k} (a_i-a_j+j-i) \quad .
$$

In fact, for any $213$-avoiding permutation (there are $C_k=(2k)!/(k!(k+1)!)$ of them) the number of ways of Playing Stanley Solitaire with initial positions
$$
[a_{\pi_1}, \dots, a_{\pi_k}] \quad,
$$
is also given by that very same expression, namely
$$
\frac{(a_1+ \dots + a_k)!}{(a_1+k-1)! (a_2+k-2)! \cdots (a_k)!} \cdot \prod_{1 \leq j < i \leq k} (a_i-a_j+j-i) \quad .
$$

If $\pi$ is not $213$-avoiding, then the formulas are no longer so nice (see below).




{\bf References}

[EG] Paul Edeleman and Curtis Greene, {\it Balanced tableaux}, Adv.  Math. {\bf 63} (1987), 42-99. \hfill\break
{\tt https://core.ac.uk/download/pdf/82733311.pdf}

[LSc] Alain Lascoux and Marcel-Paul Sch\"utzenberger, {\it Structure de Hopf de l'anneau de cohomologie et de l'anneau de Grothendick d'une
vari\'et\'e de drapeaux}, C.R. Acad. Sc. Paris {\bf 295}, S\'erie 1, 629-633. \hfill\break
{\tt http://www-igm.univ-mlv.fr/\~{}berstel/Mps/Travaux/A/1982-2HopfCras.pdf} 


[S] Richard Stanley, {\it On the number of reduced decompositions of elements of the Coxeter group},
Europ. J. Combinatorics {\bf 5} (1984), 359-372. \hfill\break
{\tt  https://math.mit.edu/\~{}rstan/pubs/pubfiles/56.pdf}



\bigskip
\hrule
\bigskip

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt ShaloshBEkhad at gmail  dot com}   \quad .
\bigskip

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt DoronZeil at gmail  dot com}   \quad .
\bigskip

Oct. 1, 2023.

\end







