Solution of American Mathematical Monthly #11929 (Oct. 2016, Proposed by Donald Knuth)

Justin SEMONSEN

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

11929 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) = ∑_{n=0}^{∞} a_{n}z^{n}. What is the asymptotic nature of a_{n} as n → ∞?

Ans.

A(z) = \frac{z (2 z^{6} + 15 z^{5} + 21 z^{4} − 38 z^{3} + 40 z^{2} − 9 z + 1)}{(z − 1)^{3} (z^{2} + 4 z − 1)^{2}} + \frac{(1 − 3z)^{2}}{(1 − 4z − z^{2})^{2}} · (1 − 4z)^{− \frac{1}{2}} .

The asymptotic of a_{n}, to order five is:

a_{n} ≍ \frac{16}{\sqrt{π}} · \frac{4^{n}}{\sqrt{n}}·

(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}} )) .

Proof: We first need a crucial lemma

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) = ∑_{r=0}^{∞} ∑_{w=0}^{3r} f(r, w)x^{r}y^{w}

is given by the rational function

F (x, y) = \frac{T op(x, y)}{Bot(x, y)} ,

where the numerator, T op(x, y), is given by

T op(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} ,

and the denominator, Bot(x, y) is given by

2 (x + 1)^{2} (xy^{2} + 1) (xy + 1) (xy^{3} + 1)^{2} (xy + xy^{2} + 1) (x − 1)^{2} (xy^{2} − 1) (xy^{3} − 1)^{2} (xy − 1) (xy + xy^{2} − 1) .

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.

Since a_{n} = f(2n, 3n), we have

A(z) = ∑_{n=0}^{∞} f(2n, 3n)z^{n} ,

is a ‘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 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 (4 z − 1) (2 z^{6} + 15 z^{5} + 21 z^{4} − 38 z^{3} + 40 z^{2} − 9 z + 1) (z − 1)^{3} A
+ (4 z − 1) (z^{2} + 4 z − 1)^{2} (z − 1)^{6} A^{2} = 0 .

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}.

Supporting Maple code can be gotten from

http://math.rutgers.edu/~zeilberg/tokhniot/DEKjs.txt .

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.

References

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

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

[Z] Doron Zeilberger, webpage of Rutgers University Experimental Mathematics (Math 640) Class, Fall 2016,

http://www.math.rutgers.edu/~zeilberg/math640 17.html .

Justin Semonsen, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: js2118 at math dot rutgers dot edu .