%knuthJ.tex: 
%%a Plain TeX file by Shalosh B. Ekhad and Doron Zeilberger (x 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\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 Solution of American Mathematical Monthly \#11929 (Oct. 2016, Proposed by Donald Knuth) }
\bigskip
\centerline
{\it Justin SEMONSEN}


In [K], Donald Knuth proposed the following intriguing  problem.

{\bf 11929} {\it Proposed by Donald Knuth, Stanford University, Stanford, CA}. Let $a_n$ be the number
of ways in which a rectangular box that contains $6n$ squares tiles in three rows of length $2n$ can be
split into two connected regions of size $3n$ without cutting any tiles. Thus $a_1=3, a_2=19, a_3=85$.
Taking $a_0=1$, find a closed form for the generating function $A(z)=\sum_{n=0}^{\infty} a_n z^n$. What is
the asymptotic nature of $a_n$ as $n \rightarrow \infty$?


{\bf Ans.} 
$$
A(z)=
{\frac {z \left( 2\,{z}^{6}+15\,{z}^{5}+21\,{z}^{4}-38\,{z}^{3}+40\,{z}^{2}-9\,z+1 \right) }{ \left( z-1 \right) ^{3} \left( {z}^{2}+4\,z-1 \right) ^{2}}}
+\frac{(1-3z)^2}{(1-4z-z^2)^2} \cdot (1-4z)^{-\frac{1}{2}} \quad .
$$
The asymptotic of $a_n$, to order five is:
$$
a_n \, \asymp  \, 
\frac{16}{\sqrt {\pi }} \cdot \frac {4^n}{\sqrt {n}}  \cdot
$$
$$
\left( 1-{\frac {169}{8}}\,{n}^{-1}+{\frac {113713}{128}}\,{n}^{-2}-{\frac {54662275}{1024}}\,{n}^{-3}+{\frac {136066657419}{32768}}\,{n}^{-4}-{
\frac {103820177963271}{262144}}\,{n}^{-5}+ O(\frac{1}{n^6}) \right) \quad .
$$

{\bf Proof}: We first need a {\bf crucial lemma}

{\bf Lemma}: 
Let $f(r,w)$  be the number of configurations (with the white and black areas both connected)
with $r$ columns and $w$ white squares (and hence $3r-w$ black squares), 
then  the bi-variate generating function
$$
F(x,y) = \sum_{r=0}^{\infty} \sum_{w=0}^{3r} f(r,w) x^r y^w 
$$
is given by the {\it rational function}
$$
F(x,y)=\frac{Top(x,y)}{Bot(x,y)} \quad ,
$$
where the numerator, $Top(x,y)$, is given by
$$
Top(x,y)=
-3\,{x}^{4}{y}^{2}-{x}^{2}{y}^{6}+4\,{x}^{4}{y}^{4}+12\,{x}^{4}{y}^{7}+8\,{x}^{6}{y}^{7}+25\,{x}^{6}{y}^{8}+8\,{x}^{6}{y}^{11}-6\,{x}^{2}y-6\,{x}^{2}{y}^{2}
$$
$$
+25\,{x}^{6}{y}^{10}-6\,{x}^{2}{y}^{4}-6\,{x}^{2}{y}^{5}-3\,{x}^{4}{y}^{10}-2\,{x}^{4}{y}^{9}+4\,{x}^{4}{y}^{8}+2\,{x}^{4}{y}^{6}+12\,{x}^{4}{y}^{5}
-6\,{x}^{2}{y}^{3}
$$
$$
+{x}^{4}-{x}^{2}-2\,{x}^{4}{y}^{3}+6\,{x}^{6}{y}^{12}+28\,{x}^{6}{y}^{9}+10\,{x}^{12}{y}^{21}+4\,{x}^{10}{y}^{21}-5\,{x}^{12}{y}^{20}+12\,{x}^{12}
{y}^{22}
$$
$$
+4\,{x}^{12}{y}^{23}-5\,{x}^{12}{y}^{16}+{x}^{8}{y}^{8}-28\,{x}^{8}{y}^{11}-9\,{x}^{8}{y}^{10}-42\,{x}^{8}{y}^{12}+6\,{x}^{6}{y}^{6}
$$
$$
-6\,{x}^{6}{y}^{
5}-6\,{x}^{6}{y}^{13}-28\,{x}^{8}{y}^{13}-9\,{x}^{8}{y}^{14}-8\,{x}^{6}{y}^{14}-7\,{x}^{8}{y}^{6}+32\,{x}^{10}{y}^{11}+35\,{x}^{10}{y}^{12}
$$
$$
-8\,{x}^{6}{y}^{4}-2\,{x}^{8}{y}^{7}-2\,{x}^{6}{y}^{15}+{x}^{8}{y}^{16}-25\,{x}^{10}{y}^{14}-38\,{x}^{10}{y}^{15}+12\,{x}^{10}{y}^{13}+35\,{x}^{10}{y}^{18}
$$
$$
-28\,{x}^{12}{y}^{18}-22\,{x}^{12}{y}^{19}+32\,{x}^{10}{y}^{19}+12\,{x}^{10}{y}^{17}-25\,{x}^{10}{y}^{16}-2\,{x}^{6}{y}^{3}-7\,{x}^{8}{y}^{18}
$$
$$
-2\,{x}^{8}{y}^{17}-4\,{x}^{8}{y}^{19}+17\,{x}^{10}{y}^{20}-22\,{x}^{12}{y}^{17}+{x}^{4}{y}^{12}-{x}^{6}{y}^{16}+17\,{x}^{10}{y}^{10}
$$
$$
-{x}^{6}{y}^{2}-4\,{x}^{14}{y}^{21}-2\,{x}^{14}{y}^{20}
$$
$$
-2\,{x}^{14}{y}^{22}+4\,{x}^{10}{y}^{9}-4\,{x}^{8}{y}^{5}+12\,{x}^{12}{y}^{14}+10\,{x}^{12}{y}^{15}+4\,{x}^{12}{y}^{13} \quad,
$$
and the denominator, $Bot(x,y)$ is given by
$$
2\, \left( x+1 \right) ^{2} \left( x{y}^{2}+1 \right)  \left( xy+1 \right)  \left( x{y}^{3}+1 \right) ^{2} \left( xy+x{y}^{2}+1 \right)  \left( x-1 \right) 
^{2} \left( x{y}^{2}-1 \right)  \left( x{y}^{3}-1 \right) ^{2} \left( xy-1 \right)  \left( xy+x{y}^{2}-1 \right) \quad .
$$

{\bf Sketch of proof}: We set-up a ``grammar'' with ten states, corresponding to how a column can be colored, and connectivity considerations,
set-up a system of ten equations and ten unknowns, add the solutions up, and get the above monster rational function. \halmos


Since $a_n=f(2n,3n)$, we have
$$
A(z)=\sum_{n=0}^{\infty} f(2n,3n) z^n \quad,
$$
is a `{\it slanted diagonal}' of the rational function $F(x,y)$ of `slope' $3/2$.
By a famous theorem of Hillel Furstenberg [F], it is guaranteed to be an algebraic formal power series, that can be easily
found by taking a certain residue, but we prefer to crank-out sufficiently many terms ($40$ suffice) of $a_n$, using $F(x,y)$,
and fit them into an algebaric equation for $A(z)$,
e.g. using Maple's {\tt gfun[listoalgeq]}  command. 
We get that $A(z)=A$ is a solution of the quadratic equation
$$
-10\,z+1-110\,{z}^{3}+178\,{z}^{5}-618\,{z}^{6}+108\,{z}^{10}+862\,{z}^{7}-485\,{z}^{8}+88\,{z}^{9}+16\,{z}^{11}+46\,{z}^{2}+116\,{z}^{4}
$$
$$
-2\,z \left( 4\,z-1
 \right)  \left( 2\,{z}^{6}+15\,{z}^{5}+21\,{z}^{4}-38\,{z}^{3}+40\,{z}^{2}-9\,z+1 \right)  \left( z-1 \right) ^{3}A
$$
$$
+ \left( 4\,z-1 \right)  \left( {z}^{2}+
4\,z-1 \right) ^{2} \left( z-1 \right) ^{6}{A}^{2} \, =0 \quad .
$$
Using the quadratic formula, taking the right solution (that is a formal power series with positive coefficients), and simplifying,
yields the closed form solution stated above for $A(z)$. Expanding $(1-4z)^{-1/2}$ by the binomial theorem, using
Stirling, and performint routine manipulations (all done automatically by Maple) produces the stated asymptotic formula
for $a_n$.


{\bf Supporting Maple code} can be gotten from

{\tt http://math.rutgers.edu/\~{}zeilberg/tokhniot/DEKjs.txt} \quad .

{\bf Acknowledgment}: 
I wish to thank Doron Zeilberger (see [Z]), for raising the challenge to solve Knuth's problem, in his "Experimental Mathematics'' class that he
is currently teaching, and I am currently taking.

\vfill\eject

{\bf References}

[F] H. Furstenberg, {\it Algebraic functions over finite fields}, J. of Algebra
{\bf 7} (1967), 271-277.

[K] Donald Knuth, {\it Proposed problem \#11929}, Amer. Math, Monthly {\bf 123} (2016), p. 831.

[Z] Doron Zeilberger, {\it webpage of Rutgers University Experimental Mathematics (Math 640) Class, Fall 2016}, \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/math640\_17.html} \quad .

\bigskip
\hrule
\bigskip
Justin Semonsen, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt js2118 at math dot rutgers dot edu}   \quad .


\end









