Combinatorics of Permutations, 2nd Edition

In One Line and Anywhere. Permutations as Linear Orders. 83

11. This result was proved in [79]. The authors showed that if p = p

1

p

2

···p

n

,

then exactly d of the n cyclic translates p

1

p

2

···p

n

, p

2

···p

n

p

1

, ···,

p

n

p

1

···p

n−1

have first entry 1 and inversion number k modulo a

1

.As

d

a

1



n−1

a

1

−1



=

d

n



n

a

1



, this proves the result. Note that the result is identi-

cal to the result of Exercise 18 (b), even if in that exercise we counted

different permutations.

12. This result was proved in [81].

13. This is a special case of a more general result of Lynne Butler [82], which

is of group-theoretical flavor. In her proof, Butler uses the interesting

fact that the number