Combinatorics of Permutations, 2nd Edition

In One Line and Close. Permutations as Linear Orders. 23

THEOREM 1.32

If a sequence of positive real numbers has real roots only, then it is log-concave.

PROOF Let a

0

,a

1

, ···,a

n

be our sequence, and let P (x)=



n

k=0

a

k

x

k

.

Then for all roots (x, y) of the polynomial Q(x, y)=



n

k=0

a

k

x

k

y

n−k

,theratio

(x/y) must be real. (Otherwise x/y would be a non-real root of P (x)). There-

fore, by Rolle’s Theorem, this also holds for the partial derivatives ∂Q/∂x and

∂Q/∂y. Iterating this argument, we see that the polynomial ∂

a+b

Q/∂x

a

∂y

b

also has real zeros, if a + b ≤ n − 1. In particular, this is true in the special

case when a = j − 1, and b = n − j − 1, for some fixed ...