78 Combinatorics of Permutations, Second Edition
28. Let n<k≤
n
2
.Provethat
b(n +1,k)=b(n +1,k− 1) + b(n, k) − b(n, k − n −1).
29. (+) Find a formula for
n
k=0
(−1)
k
n
k
.
30. (+) Consider the following refinement of the Eulerian polynomials. Let
A
n,k
(q)=
p
q
maj(p)
,
where the sum is taken over all n-permutations having k − 1 descents.
These polynomials are often called the q-Eulerian polynomials. Prove
that
[x]
n
=
n
k=1
A
n,k
(q)
x + n − k
n
.
31. Let p be a permutation of length n − 1. Insert the entry n into all p
in all possible ways. This yields n distinct permutations of length n.
Compute the major index of each of these permutations. Prove that all
these n major indices will be distinct, and that their set will be the set
of integers in the interval [maj(p