Problem 11929
(American Mathematical Monthly, Vol.123, October 2016) Proposed by D. Knuth (USA).
Let an be the number of ways in which a rectangular box that contains 6n square tiles in three rows of length2n can be split into two connected pieces of size 3n without cutting any tiles. Thus, a1 = 3, a2 = 19, and a3 = 85. Taking a0 = 1, find a closed form for the generating function A(z) =P∞
n=0anzn. What is the asymptotic nature ofan as n → ∞?
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Solution.
We divide the counting with respect to what can be found in the first column and in the last column of the 3 × 2n board. For each case we give the corresponding generating function.
In the following diagrams, we assume that the lower left corner is a always a black square.
Moreover,
i) is one black square and is one white square;
ii) represents an horizontal group of adjacent black squares of non-negative length;
iii) represents an horizontal group of adjacent black squares over which we may arrange a not greater number of black squares (not necessarily adjacent).
1)
2n−2
A1(z) =
∞
X
n=1
2n − 2 n − 1
zn= z
√1 − 4z.
2)
2n−2
A2(z) =
∞
X
n=1
2n − 2 n
zn=1
2
√1 − 2z 1 − 4z − 1
.
3)
a b
A3(z) =
∞
X
n=1
zn·
"2n−1 X
a=1 2n−a−1
X
b=0
0
n − 2a − b
a b
c
+
2n−2
X
a=1 2n−1−a
X
c=1
(c−2)∨0
X
b=0
2n − 1 − a − c n − 1 − 2a − b
= z
1 − 4z − z2
1 − 1 − 3z − z2
√1 − 4z
.
4)
a b
A4(z) =
∞
X
n=1
zn·
"2n−1 X
a=1 2n−a−2
X
b=0
0
n − 1 − 2a − b
a b
c
+
2n−2
X
a=1 2n−1−a
X
c=1
(c−2)∨0
X
b=0
2n − 1 − a − c n − 2 − 2a − b
= 1
2(1 − 4z − z2)
(2 − 5z − z2) −(1 − z)(2 − 7z − 2z2)
√1 − 4z
.
5)
a
b b′
a′
A5(z) = 2
∞
X
n=1
zn·
2n−1
X
a=1 2n−a
X
a′=1
2n−a−a′
X
b=0
2n−a−a′−b−1
X
b′=0
0
n − 2a − 2a′− b − b′
a b
c b′
a′
+
2n−1
X
a=1 2n−a
X
a′=1
2n−a−a′
X
c=1
(c−2)∨0
X
b=0
(2n−a−a′−c−1)∨0,
X
b′=0
0
n − 2a − 2a′− b − b′− 1
a b
c c′
b′
a′
+
2n−1
X
a=1 2n−a
X
a′=1
2n−a−a′−c
X
c′=1
2n−a−a′
X
c=1
(c−2)∨0
X
b=0
(c′−2)∨0,
X
b′=0
2n − a − a′− c − c′ n − 2 − 2a − 2a′− b − b′
= 1
(1 − 4z − z2)2
4 − 28z + 49z2− 11z4− 2z5
√1 − 4z − (2 − 3z − z2)(2 − 7z − z2)
.
6)
a b b′
A6(z) = 1 +
∞
X
n=1
zn·
"2n−1 X
a=1 2n−1−a
X
b=0
2n−1−a
X
b′=0
0
3n − 3a − b − b′
a b
+
2n−2
X
a=1 2n−1−a
X
b=1
0
3n − 3a − b
a b
c e
+2
2n−3
X
a=1 2n−2−a
X
c=1
2n−1−a−c
X
e=1
(c−2)∨0
X
b=0
0
3n − 1 − 3a − b − c − e
a b
c d
+2
2n−1
X
a=1 2n−1−a
X
c=1
2n−1−a−c
X
d=0
(c−2)∨0
X
b=0
d
3n − 1 − 3a − b − c − d
a b
c d e
+2
2n−1
X
a=1 2n−3−a
X
c=1
2n−3−a−c
X
d=0
2n−1−a−c−d
X
e=2
(c−2)∨0
X
b=0
d
3n − 2 − 3a − b − c − d − e
= 1
1 − 4z − z2
1 − 6z + 20z2− 20z3+ 11z4+ 2z5
(1 − z)3 −2z2(z + 2)
√1 − 4z
.
Hence the total generating function is
A(z) = 2A1(z) + 2A2(z) + 4A3(z) + 4A4(z) + A5(z) + A6(z) that is
A(z) = 1
(1 − 4z − z2)2
(1 − 3z)√ 2
1 − 4z −z(1 − 9z + 40z2− 38z3+ 21z4+ 15z5+ 2z6) (1 − z)3
.
It can be seen that A is analytic in |z| < 1/4 (the roots of 1 − 4z − z2, i. e. −2 ±√
5, are removable singularities). Hence, by Darboux’s Lemma (see p.179 in Generatingfunctionology),
an = [zn]A(z) ∼
(1 − 3z)2 (1 − 4z − z2)2
z=1
4
· 4nn −12
n
∼ 16 · 4n
√nπ .
Note that the first terms of the sequence (OEIS A167242) are:
1, 3, 19, 85, 355, 1435, 5717, 22645, 89521, 353735, 1397863, 5525341, 21846421, 86403027, 341822335, 1352660761, 5354124895, 21197945407, 83945924393, 332507403625, 1317329758675, 5220055148883.
