28 Combinatorics of Permutations, Second Edition
(x + 1)(10x
2
+2x), and that
G
5
(x)=32x
4
+58x
3
+28x
2
+2x =(x + 1)(32x
3
+26x
2
+2x).
Further analysis shows that G
6
(x)andG
7
(x) are divisible by (x +1)
2
,and
that G
8
(x)andG
9
(x) are divisible by (x +1)
3
, and so on. In general, it
seems that for any positive integer n ≥ 4, the polynomial G
n
(x) is divisible
by (x +1)
(n−2)/2
.
This is an interesting observation, and one that is certainly of combinatorial
flavor. For instance, if we just wanted to prove that G
n
(x) is divisible by x+1,
we could proceed as follows. We could arrange our permutations into pairs, so
that each pair consists of two permutations, one with r alternating runs, and
one with r + 1 alternating runs. If we could do that, that would imply that
G
n
(x)=( ...