/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 271-275 https://doi.org/10.26493/1855-3974.1901.987
(Also available at http://amc-journal.eu)
Logarithms of a binomial series: A Stirling number approach
Helmut Prodinger
Department of Mathematics, University of Stellenbosch, 7602, Stellenbosch, South Africa
Received 8 January 2019, accepted 21 April 2019, published online 15 October 2019
Abstract
The p-th power of the logarithm of the Catalan generating function is computed using the Stirling cycle numbers. Instead of Stirling numbers, one may write this generating function in terms of higher order harmonic numbers.
Keywords: Catalan numbers, logarithm, generating function, Stirling number. Math. Subj. Class.: 05A15, 05A10
1 Introduction
Knuth [6, 7] proposed the exciting formula
(log C(z))2 = £ f2n) (H2n_i - Hn)-
where
and
= = E n+r(2r>" <■■»
n>0	V 7
h = e k
1 <k<n
with the generating function of Catalan numbers and harmonic numbers.
This formula was recently extended by Chu [1] to general exponents p. Chu's approach is based on the use of (exponential) Bell polynomials. Note that Knuth talked about the exponent 1 in his Christmas lecture from 2014 [5].
E-mail address: hproding@sun.ac.za (Helmut Prodinger) ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
271
250	Ars Math. Contemp. 17 (2019) 291-310
We present here a very simple approach to this question using Stirling cycle numbers; recall [3] that they transform falling powers into ordinary powers viz.
E
0< k<n
(-1)
n—k xk
For the readers' convenience it is mentioned that the numbers [k] (-1)n k appear often in the older literature as s(n, k) and are then denoted as Stirling numbers of the first kind.
2 The expansion of the p-th power
The substitution z
(1_t"u)2 was presented in [2] and it is extremely useful when dealing with Catalan numbers and Catalan statistics. Using it in (1.1), we get C(z) = 1 + u, and, by the Lagrange inversion formula [8],
mi 2n

n Vn — m
for m > 1. For m = 0 the formula is still true when taking a limit. We now consider the bivariate generating function
aP
F(z, a) = V — (log C(z))p = exp(alogC(z))
Z—/ p!
p>0
=c a(z)=(1+u)«=e (m)
m>0 V 7
But
Therefore
ml m!
A= m E (-1)
m!	m! z—'
m—k
0< k<r,
ak.
F(z.«)= E m^(-1)
m—k
0< k<m< n
k
m 2n
n n m
The desired formula follows from reading off coefficients of ap:
(log C(z))p = p![ap]F (z,a)= £ ^,(-1)
m!
p<m<n
m 2n
n n m
(2.1)
3 Special cases
For p =1 in equation (2.1), we get the instance of the Christmas lecture:
log C(z) = a]F(z, a) = E -(-1)
m!
m —1
K m<n
2n
n n m
Since [r^] = (m - 1)!, this leads to
log C(z) = [a1]F(z, a) = 1 E "(^V'
n> 1 ^ '
n
X
m
u
a
zn.
m
m—p
zn.
p
m
n
z
H. Prodinger: Logarithms of a binomial series: A Stirling number approach
273
Now we turn to the instance p = 2 from [6, 7]. (Note that = (m - 1)!Hm-1.) Equation (2.1) leads to
2[a2]F(z,a) = V A(-1)m M^ ) 1 J V ' y ^ mV ' 2 n In - m
2<m<n	L J \	/
m 2n
zn
= 2 V Hm_i( —1)m V 2n )zn n n m
2<m<n	v	7
= 2 V 1(-1)m 1 f2n y
j	n\n — m
1 <j<m<n J	v	7
= 2 E 1(-1)j-1 ^ f 2n- 1]lzn
z—' j	n \n — j — 1
1<j<n
In the last step we used the formula
2n A	, -, f 2n - 1
(-1)"M
n
j<" <n
F (-1)" 2n =(-1)j"\ . 1
\n - mj v 7 Vn - j - 1
which is a standard summation for binomial coefficients [3].
To obtain the form proposed by Knuth, we still need to prove that
f2"Wi - Hn) = 2 V l-ir1 f 2n - 1
\n	z—' j V n — j — 1
v 7	1<j<n j	\ j
Modern computer algebra systems readily simplify the difference of these two sides to 0, as expected.
4 Connection with harmonic numbers — the general case
In [4], there is the general formula
1
n!
n + 1 r + 1
(-1)r vn tHiif Hn '
I, !
{r} j=1 j
Here, the sum is over all partitions of r:
r = iiri +-----+ ii ri,
with parts r1 > • • • > ri > 1 and positive integers i1,..., ii. As an example, the partitions
of r = 4 are 4, 3 + 1, 2 + 2, 2+1 + 1,1 +1 +1 +1, written alternatively as 1 • 4,1 • 3 + 1 • 1, 2 • 2, 1 • 2 + 2 • 1, 4 • 1.
There appear higher order harmonic numbers as well:
hp = y -1.
n ^ k-
1< k<n
275
Ars Math. Contemp. 17 (2019) 291-310
Here are the first few instances:
Hn,
1
n! 1
n! 1
n! 1
n!
n + 1 2
n + 1
3
n + 1
4
n + 1
5
= -1H2) + 1H2 2 Hn + 2 Hn '
= 1H (3) — 1H (2)H + 1H 3 3 Hn 2 Hn Hn + g Hn,
= -1 H(4) + 1 H^Hn + 1 (H^)2 - 1 H^Hn + ^Hn.
1
1
21
24
This allows to replace (m-1)! in (log C (z))p = £
p<m<n
(m - 1)!
(-1)m-p2n n n m
by an expression involving H^l^ ..., H^P-^.
5 Extension
If instead of u = z(1 + u)2 we work with u = z(1 + u)\ then we deal with the generating function of extended (generalized) Catalan numbers
Ca(Z) = £
2>0
1 + nA\ z
n / 1 + nA
From [3], we infer that
E/ An + m \ m I	I--zn.
nm
V n / An + m
So
— (log CA(z))p = exp(a log CA(z)) = C£(z) p!
p>0
(1+u)a = £
0
E ^(-1)
m!
m-k
0< k<m<n
An + m m
n An + m
The desired formula follows from reading off coefficients of ap:
(log CA(z))p = p![ap ]F (z,a) = E "Pr(-1)
m!
m-p
pKmKn
An + m m
n An + m
1
m
P
n
m
U
a
m
U
m
k
a
H. Prodinger: Logarithms of a binomial series: A Stirling number approach
253
References
[1]	W. Chu, Logarithms of a binomial series: extension of a series of Knuth, Math. Commun. 24 (2019), 83-90, https://www.mathos.unios.hr/mc/index.php/mc/article/ view/2878.
[2]	N. G. de Bruijn, D. E. Knuth and S. O. Rice, The average height of planted plane trees, in: R. C. Read (ed.), Graph Theory and Computing, Academic Press, New York, pp. 15-22, 1972.
[3]	R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 2nd edition, 1994, https://www-cs-faculty.stanford.edu/ ~knuth/gkp.html.
[4]	D. B. Grunberg, On asymptotics, Stirling numbers, gamma function and polylogs, Results Math. 49 (2006), 89-125, doi:10.1007/s00025-006-0211-7.
[5]	D. E. Knuth, (3/2)-ary Trees (20th Annual Christmas Tree Lecture), 2014, https://www. youtube.com/watch?v=P4AaGQIo0HY.
[6]	D. E. Knuth, Problem 11832 (Problems and Solutions), Amer. Math. Monthly 122 (2015), 390, doi:10.4169/amer.math.monthly.122.04.390.
[7]	D. E. Knuth, Log-squared of the Catalan generating function (Solution to Problem 11832), Amer. Math. Monthly 124 (2017), 660-661, doi:10.4169/amer.math.monthly.124.7.659.
[8]	R. P. Stanley, Enumerative Combinatorics, Volume I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole, Monterey, California, 1986, doi:10.1007/ 978-1-4615-9763-6.