KIRKMAN’S HYPOTHESIS REVISITED

Alois Panholzer

Institut für Algebra und Computermathematik, Technische Universität Wien, Wiedner Hauptstraße

8–10 A- 1040 Wien, Austria

                      Alois.Panholzer@tuwien.ac.at

Helmut Prodinger^{∗}

The John Knopfmacher Centre for Applicable Analysis and Number Theory, Mathematics Department,

University of the Witwatersrand, P.O. Wits 2050 Johannesburg, South Africa

                       helmut@gauss.cam.wits.ac.za

Received: 6/1/01, Revised: 7/17/01, Accepted: 7/26/01 , Published: 7/31/01

Abstract

Watson proved Kirkman’s hypothesis (partially solved by Cayley). Using Lagrange Inversion, we drastically shorten Watson’s computations and generalize his results at the same time.

Kirkman’s hypothesis [3] is (in changed notation) the formula

∑_{m=0}^{M} ∑_{n=0}^{N} \frac{1}{m + 1}\binom{m + n}{n}\binom{2m + n + 2}{m + n + 2} \frac{1}{M − m + 1}\binom{M − m + N − n}{N − n}\binom{2(M − m) + N − n + 2}{M − m + N − n + 2}

= \frac{2}{M + 2}\binom{M + N + 1}{N}\binom{2M + N + 4}{M + N + 4} .

Kirkman could not prove it, but Cayley [1] proved the special case N = 0 in 1857. After more than hundred years, Watson [5] proved Kirkman’s hypothesis by establishing the following power series expansions. Set

ψ(z, w) := \frac{1 − w − 2z − \sqrt{(1 − w)^{2} − 4z}}{2z(z + w)} ,

∗WWW-address: http://www.wits.ac.za/helmut/index.htm

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A05 2

then

ψ(z, w) = ∑_{m,n} \frac{1}{m + 1}\binom{m + n}{n}\binom{2m + n + 2}{m + n + 2}z^{m}w^{n} ,

ψ^{2}(z, w) = ∑_{m,n} \frac{2}{m + 2}\binom{m + n + 1}{n}\binom{2m + n + 4}{m + n + 4}z^{m}w^{n} .

Of course, Kirkman’s hypothesis follows from this by writing ψ·ψ = ψ^{2} and comparing coefficients.

However, Watson’s derivation of these two expansions required quite a bit of computation, in particular he treated both cases differently and separately.

Here, we present an extremely simple computation using the Lagrange inversion formula that has the advantage of not only treating both cases together but rather finding the power series expansion for ψ^{p}(z, w) for general p. We refer for the Lagrange inversion formula to [2, 6]; the version that is sufficient for our purposes is this: If

y = zΦ(y),

then

[z^{n}]y^{p} = \frac{p}{n}[y^{n−p}](Φ(y))^{n}

([z^{n}]f(z) means the coefficient of z^{n} in the series expansion of f(z)).

The quadratic equation satisfied by ψ(z, w) is

z(z + w)ψ^{2}(z, w) + (2z + w − 1)ψ(z, w) + 1 = 0 .

Writing ψ = y/z and rearranging leads to the following equation of Lagrange type:

y = z \frac{(1 + y)^{2}}{1 − w(1 + y)} .

With the Lagrange inversion formula we obtain:

[z^{m}w^{n}]ψ^{p}(z, w) = [z^{m+p}w^{n}]y^{p}(z, w) = \frac{p}{m + p}[y^{m}w^{n}] (\frac{(1 + y)^{2}}{1 − w(1 + y)})^{m+p}

= \frac{p}{m + p}\binom{m + n + p − 1}{n}[y^{m}](1 + y)^{2m+n+2p}

= \frac{p}{m + p}\binom{m + n + p − 1}{n}\binom{2m + n + 2p}{m + n + 2p} .

This leads, with r + s = p and ψ^{r} · ψ^{s} = ψ^{p}, to the convolution formula (generalized Kirkman hypothesis):

∑_{m=0}^{M} ∑_{n=0}^{N} \frac{r}{m + r} \binom{m + n + r − 1}{n}\binom{2m + n + 2r}{m + n + 2r} ×

× \frac{s}{M − m + s}\binom{M − m + N − n + s − 1}{N − n}\binom{2(M − m) + N − n + 2s}{M − m + N − n + 2s}

= \frac{p}{M + p}\binom{M + N + p − 1}{N}\binom{2M + N + 2p}{M + N + 2p} .

For other results of Kirkman’s, treated with the Lagrange inversion formula, see [4, Ex. 6.33-c].

References

[1] A. Cayley, Note on the summation of a certain factorial expression, Collected Math. Papers 3 (1890), 250–253.

[2] I. Goulden and D. Jackson, Combinatorial enumeration, John Wiley, 1983.

[3] T. P. Kirkman, On the K–partitions of the R–gon and R-ace, Phil. Trans. Royal Soc. 147 (1857), 217–272.

[4] R. Stanley, Enumerative combinatorics. Vol. 2, Cambridge University Press, Cambridge, 1999.

[5] G. N. Watson, A proof of Kirkman’s hypothesis, Proc. Edinb. Math. Soc., II. Ser. 13 (1962), 131–138.

[6] H. S. Wilf, generatingfunctionology, 2nd Edition, Academic Press, 1994.