Problem 11403
(American Mathematical Monthly, Vol.115, December 2008) Proposed by Yaming Yu (USA).
Letn be an integer greater than 1, and let fn be the polynomial given by
n
X
i=0
n i
(−x)n−i
i−1
Y
j=0
(x + j).
Find the degree offn.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Leti
k be the Stirling number of first kind which counts the number of permutations of {1, 2, . . . , i}
with k-cycles. Since
i−1
Y
j=0
(x + j) = xi=
i
X
k=0
i k
xk then the coefficient of xmin fn is
an,m=
n
X
i=0
n i
(−1)n−i
i
m − (n − i)
=
n
X
k=0
(−1)kn k
n − k m − k
.
Note that nkn−k
m−k is the number of permutations of {1, 2, . . . , n} which have m cycles with at least k fixed points (a fixed point is a cycle of length 1): nk is the number of ways of choosing k fixed points andn−k
m−k is the number of ways of completing the permutation with other m − k cycles.
Hence the formula of an,m can be seen as an application of the Inclusion-Exclusion Principle and it follows that an,m is the number of permutations of {1, 2, . . . , n} with m cycles of length greater than 1. So, an,m= 0 when 2m > n that is if m > ⌊n/2⌋ and an,m> 0 when m = ⌊n/2⌋ because
(1, 2)(3, 4) . . . (n − 1, n) for n even and (1, 2)(3, 4) . . . (n − 2, n − 1, n) for n odd have ⌊n/2⌋ cycles of length greater than 1.
Hence the degree of fn is ⌊n/2⌋.
