
In One Line and Close. Permutations as Linear Orders. 43
44. (+) Keep the notation of the previous exercise, and let
C
n
(x)=
n
i=1
C
n,i
x
i
.
Prove that for all positive integers n, the roots of the polynomial C
n
(x)
are all real, distinct, and non-positive.
45. (–) Find a direct combinatorial proof (no generating functions, no al-
ternating runs) for the fact that for n ≥ 2, the number as(p) is even for
exactly half of all n-permutations p.
46. A permutation p = p
1
p
2
···p
n
is called a simsun permutation if there
exists no k ≤ n so that removing the entries larger than k from p,the
remaining permutation has two descents in consecutive positions. For
instance,