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) = x^{i}=

i

X

k=0

i k

x^{k}
then the coefficient of x^{m}in fn is

an,m=

n

X

i=0

n i

(−1)^{n−i}

i

m − (n − i)

=

n

X

k=0

(−1)^{k}n
k

n − k m − k

.

Note that ^{n}_{k}_{n−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): ^{n}_{k} is the number of ways of choosing k fixed
points and_{n−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⌋.