Problem 12219
(American Mathematical Monthly, Vol.127, December 2020) Proposed by B. Isaacson (USA).
Let k and m be positive integers with k < m. Let c(m, k) be the number of permutations of {1, . . . , m} consisting of k cycles. The numbers c(m, k) are known as unsigned Stirling numbers of the first kind. Prove
m
X
j=k
(−2)j mjc(j, k) (j − 1)! = 0 whenever m and k have opposite parity.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Solution. Let
Fm(x) =
m
X
k=1
(−x)k
m
X
j=k
(−2)j mjc(j, k) (j − 1)!
then it suffices to show that the polynomial Fmis even when m is even and it is odd when m is odd, that is
F(−x) = (−1)mF(x).
We have that
Fm(x) :=
m
X
j=1
2j mj (j − 1)!
j
X
k=1
(−1)j−kc(j, k)xk
=
m
X
j=1
2j mj
(j − 1)!· x(x − 1) · · · (x − j + 1)
= m
m
X
j=1
2jm − 1 j− 1
x j
= m
m
X
j=0
2jm − 1 m− j
x j
= m[zm] (1 + z)m−1(1 + 2z)x
= m[zm] (1 + z)x+m−1
1 + z
1 + z
x
= m
m
X
j=0
x + m − j − 1 m− j
x j
.
Therefore, since −yr = (−1)r y+r−1r , it follows that
Fm(−x) := m
m
X
j=0
−x + m − j − 1 m− j
−x j
= m
m
X
j=0
−(x − j + 1) j
−x m− j
= m
m
X
j=0
(−1)jx j
· (−1)m−jx + m − j − 1 j
= (−1)mF(x)
and the proof is complete.