Combinatorics of Permutations, 2nd Edition

68 Combinatorics of Permutations, Second Edition

2.2 Inversions in Permutations of Multisets

Instead of permuting the elements of our favorite set, [n], in this section

we are going to permute elements of multisets. We will use the notation

{1

a

1

, 2

a

2

, ···,k

a

k

} for the multiset consisting of a

i

copies of i, for all i ∈ [k].

For our purposes, a permutation of a multiset is just a way of listing all its

elements. It is straightforward to see, and is proved in most undergraduate

textbooks on enumerative combinatorics, that the number of all permutations

of the multiset K = {1

a

1

, 2

a

2

, ···,k

a

k

} is

n!

a

1

!a

2

! ···a

k

!

,

where n = a

1

+ a

2

+ ···+ a

k

.

An inversion of