
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