Permutations of Multisets: a 10 minute video by Ma Yu Chun

A permutation of multisets is a permutation with repeated inclusion of a finite number of elements of different types.

For example, how many permutations are there of the 8 letter word "pingpang"? There are two "p"s, "n"s, and "g"s. We need to divide by the redundancy. So the answer is (8; 2, 2, 2, 1, 1) = 8!/2!2!2!1!1! = 5040.

The permutation of r1 1s, r2 2s, ... rt ts such that r1+r2+···+rt=n is denoted P(n;r1,r2,...,rt) = n!/r1!r2!···rt!. Effectively, we are dividing the permutations of n by the possible arrangements of labels for the repeated elements.

The binomial theorem says that (a+b)^n = Σ(0≤k≤n) n!/k!(n-k)!a^kb^(n-k) = Σ(0≤k≤n) C(n,k)a^kb^(n-k). If we label all the k "a"s and the n-k "b"s, we can see the binomial coefficient as a permutation of multisets.

The multinomial theorem says that (a1+a2+···+at)^n = Σ P(n;r1,r2,...,rt)a1^(r1)a2^(r2)···at^(rt) where Σri = n. It generalizes the binomial theorem using the permutation of multisets.

How many ways can 9 pingpangs be distributed into 6 holes or areas if order matters?

We can use the bar method. 5 bars are needed to partition 6 areas. If we label the bars, we would have 5 + 9 = 14 labeled elements. We can now consider the problem as a permutation of multisets. There are P(14;5,1,1,1,1,1,1,1,1,1) = 14!/5! = 726,485,760

Another way to get this result is to look at choosing the area each ball goes into as a 9 step process. The first ball has 6 areas to choose. Because order matters, ball 2 could go on either side of ball 1. So there are 7 choices for ball 2. Since each ball adds another choice, we have 6*7*8*9*10*11*12*13*14 choices for the 9 balls. That is, 14!/5!.

http://www.youtube.com/watch?v=Vguc-AXJ_YY

Subtitles: http://cjfearnley.com/TsinghuaX60240013.x/week2/Week2.00005.TSGCMATHT314-V001300_100.srt

From the free on-line course: https://www.edx.org/course/combinatorial-mathematics-zu-he-shu-xue-tsinghuax-60240013x-2

Lecture: Week 5, Combinatorial trip of a Pingpang ball, Various Permutations, Permutations of Multisets