some of the elements might be repeated.
Sometimes, not only could the elements
be repeated, but the number of
each kind of elements is limited.
It's called permutations of multisets.
Let's look at this problem:
How many permutations are there
for word "pingpang"? P I N G P A N G
There are repetitions in this word.
How many letters are repeated?
There are 2 p's, 2 n's and 2 g's.
The number of these repeated elements
are limited.
We don't know how to calculate permutations of multisets,
but we do know how to calculate
permutations without repetitions.
So could we turn these repeated elements
into different ones?
Actually, it's quite simple.
For example, label the two p's as p1 and p2,
after calculating the permutations w/o repetitions,
we could get the permutations of multisets
by dividing the redundancy rate.
Well,
we label the two p's as p1 and p2,
n ⇒ n1 n2
g ⇒ g1 g2
and i, a.
Now we just calculate the permutations
without repetition and the result is 8!.
What's the redundancy rate?
For p,
there are two p's so it's 2!.
n ⇒ 2! g ⇒ 2!
So now we could deal with permutations of multisets.
We denote it as:
Pn add a semicolon
then use r1 r2 and so on to denote the number of each elements.
For the word "ping pang",
it contains 8 letters,
in which there are 2 n's, 2 g's and 2 p's.
So we write it as 8 2 2 1 1.
For such a permutation of multiset,
after labeling,
we could know that
the number of permutations w/o repetition is 8!,
then we divide it by the redundancy rate of each elements,
divide it by 2! 2! 2!.
Finally we could calculate the permutation of multisets,
the result is 8! / (2!×
2!×2!)
This is the number of permutations
for "pingpang".
Not only could the method we just used
deal with the permutations of English words,
but also a lot of other things.
Especially, we could apply it
to polynomial expansion.
In order to use it more generally,
we'd give it a formal definition.
What's permutation of multisets?
For multiple elements
r1 1's, r2 2's, ..., rt t's.
The total number of elements is n.
The permutation is denoted as P(n;r1,r2
...,rt)
It's equal to P(n,n) divided by
(r1!×r2!×⋯×rt!)
We could understand it as dividing the permutations of n
by the arrangements of labels after labeling the repeated elements.
Now let's rethink binomial theorem
with it.
Binomial theorem: a term in the
expansion of (a+b)^n is
a^k×b^(n-k).
The coefficient of each term
is actually equal to a permutation with repetitions
in which there are k a's and (n-k) b's.
Of course we could label all the k a's
and all the (n-k) b's.
According to the permutation of multisets we just studied,
the coefficient of this term is equal to
n! divided by k!
and (n-k)!.
So we just viewed the binomial theorem
with another perspective.
Could we extend the theorem
to the exponentiation of more then two terms?
Maybe we could deal with (a1+a2
⋯at)^n.
How would its coefficients be?
A term of its expansion is a1^r1
×a2^r2
⋯×at^rt.
The coefficient of this term
is the number of arrangements of the
permutation of r1 a1's, r2 a2's ...
According to the calculation we just conducted,
the permutation of n is n!.
So it's n! divided by r1!
×r2!×⋯×rt!
Thus we could get the coefficient
of a term in a polynomial expansion.
Next, let's look at a game.
This game
is quite popular at game centers.
Let's take ping pong balls as example.
There are 6 tracks
which are corresponding to 6 holes.
Now
we have 9 balls
with labels 1...9.
We'd send them into the 6 different
holes via the corresponding tracks.
If order matters, how many arrangements
are there for the balls to go into the holes?
This problem looks complex,
it seems that there are a lot of situations.
Let's analyze it.
According to the order,
the 9 balls are distributed into 6 areas.
How should we represent these 6 areas?
Actually we have a masterly method,
with is called the bar method.
To obtain 6 areas,
we need 5 bars to
partition it.
So sending the 9 balls
to the 6 areas in order
is equal to
that there are already 6 areas
and we are going to fill 1,2,3,4...
into these areas
like this.
This animation is an
arrangement.
So how should we denote such arrangements?
Actually, the bars
are the same,
but all the other elements,
which are number 1 ... 9, have no repetitions.
It seems that in this permutation,
there are both non-repeated elements
and repetitions.
We just learned in permutations of multisets that
if there are repeated elements
we have a good method
which is to label the repeated elements and then
divide the total number of permutations with the redundancy rate.
It's the same here,
although all the bars are the same,
we could label them
so we convert this problem into a permutation without repetitions.
So now we find out that
this problem is actually quite simple.
At first there are
5 bars and 9 numbers
so there are a total of 14 different elements.
They formed a permutation of 14, which is 14!.
Then
we need to divide it by the redundancy rates of labels.
So the 14!/5!
is the answer.
It gives us a new idea
that for some partition-related problems,
we could use the bar method
to find the answer easily.
Some of you might not be familiar with this method,
are there any other methods?
We would also do the partition,
and then we could try to analyze by steps
to obtain the answer.
As we already have 6 ares,
how many choices are there for the first ball?
It might be in area 1 ... area 6.
There are 6 ways.
After settling the first ball,
let's see ..
this is the situation for the second ball.
How many areas are there now?
Actually ball 1 partitioned an area
into two.
So for ball 2,
it might be at the left of ball 1,
or at the right of ball 1.
So in this situation,
there are more arrangements for ball 2,
it could be sent to 7 different positions.
So forth,
after ball 1 and ball 2 are settled,
there's one more choice for ball 3,
there are 8 areas for it.
So forth... until the last ball.
How about the last ball?
There are 14 choices for it.
So the answer is to multiply from 6
to 14.
It's equal to 14!/5!,
which is the same as what we got by the first method.
So we've found that although the concept
of permutation is simple
there are a lot of skills.
For problems with limitations of adjacency,
we need to bind some elements together.
For problems with multiple areas,
we would usually use the bar method.
Of course there are many other methods.
Hopefully, after practicing,
we could find more skillful methods.
Next time we would introduce
many more methods for combination.