0
00:00:02,238 --> 00:00:05,358
some of the elements might be repeated.

1
00:00:05,518 --> 00:00:07,598
Sometimes, not only could the elements

2
00:00:07,638 --> 00:00:09,718
be repeated, but the number of

3
00:00:09,758 --> 00:00:11,878
each kind of elements is limited.

4
00:00:11,918 --> 00:00:14,718
It's called permutations of multisets.

5
00:00:15,038 --> 00:00:16,918
Let's look at this problem:

6
00:00:17,118 --> 00:00:21,998
How many permutations are there

7
00:00:22,038 --> 00:00:26,038
for word "pingpang"? P I N G P A N G

8
00:00:26,998 --> 00:00:31,158
There are repetitions in this word.

9
00:00:31,438 --> 00:00:32,718
How many letters are repeated?

10
00:00:32,758 --> 00:00:37,678
There are 2 p's, 2 n's and 2 g's.

11
00:00:38,318 --> 00:00:41,158
The number of these repeated elements

12
00:00:41,198 --> 00:00:43,158
are limited.

13
00:00:43,438 --> 00:00:46,838
We don't know how to calculate permutations of multisets,

14
00:00:46,878 --> 00:00:49,918
but we do know how to calculate

15
00:00:49,958 --> 00:00:51,158
permutations without repetitions.

16
00:00:51,198 --> 00:00:54,718
So could we turn these repeated elements

17
00:00:54,758 --> 00:00:56,318
into different ones?

18
00:00:57,438 --> 00:00:59,798
Actually, it's quite simple.

19
00:00:59,838 --> 00:01:05,616
For example, label the two p's as p1 and p2,

20
00:01:06,675 --> 00:01:09,238
after calculating the permutations w/o repetitions,

21
00:01:09,278 --> 00:01:12,718
we could get the permutations of multisets

22
00:01:12,758 --> 00:01:15,918
by dividing the redundancy rate.

23
00:01:15,958 --> 00:01:17,118
Well,

24
00:01:17,158 --> 00:01:20,118
we label the two p's as p1 and p2,

25
00:01:20,158 --> 00:01:21,958
n ⇒ n1 n2

26
00:01:21,998 --> 00:01:23,238
g ⇒ g1 g2

27
00:01:23,278 --> 00:01:25,278
and i, a.

28
00:01:25,318 --> 00:01:28,038
Now we just calculate the permutations

29
00:01:28,198 --> 00:01:32,158
without repetition and the result is 8!.

30
00:01:32,198 --> 00:01:34,078
What's the redundancy rate?

31
00:01:34,118 --> 00:01:35,358
For p,

32
00:01:35,398 --> 00:01:37,598
there are two p's so it's 2!.

33
00:01:37,638 --> 00:01:40,678
n ⇒ 2!  g ⇒ 2!

34
00:01:40,718 --> 00:01:44,958
So now we could deal with permutations of multisets.

35
00:01:45,198 --> 00:01:47,918
We denote it as:

36
00:01:47,958 --> 00:01:51,958
Pn  add a semicolon

37
00:01:51,998 --> 00:01:56,118
then use r1 r2 and so on to denote the number of each elements.

38
00:01:56,158 --> 00:01:58,318
For the word "ping pang",

39
00:01:58,358 --> 00:02:01,158
it contains 8 letters,

40
00:02:01,198 --> 00:02:07,598
in which there are 2 n's, 2 g's and 2 p's.

41
00:02:07,638 --> 00:02:11,638
So we write it as 8 2 2 1 1.

42
00:02:11,838 --> 00:02:13,718
For such a permutation of multiset,

43
00:02:13,758 --> 00:02:15,518
after labeling,

44
00:02:15,558 --> 00:02:17,278
we could know that

45
00:02:17,318 --> 00:02:19,718
the number of permutations w/o repetition is 8!,

46
00:02:19,758 --> 00:02:23,958
then we divide it by the redundancy rate of each elements,

47
00:02:23,998 --> 00:02:26,758
divide it by 2! 2! 2!.

48
00:02:26,798 --> 00:02:30,038
Finally we could calculate the permutation of multisets,

49
00:02:30,078 --> 00:02:33,398
the result is 8! / (2!×

50
00:02:33,438 --> 00:02:35,278
2!×2!)

51
00:02:35,318 --> 00:02:37,238
This is the number of permutations

52
00:02:37,278 --> 00:02:40,358
for "pingpang".

53
00:02:41,198 --> 00:02:43,078
Not only could the method we just used

54
00:02:43,118 --> 00:02:46,518
deal with the permutations of English words,

55
00:02:46,838 --> 00:02:49,398
but also a lot of other things.

56
00:02:49,438 --> 00:02:50,958
Especially, we could apply it

57
00:02:50,998 --> 00:02:53,038
to polynomial expansion.

58
00:02:53,318 --> 00:02:55,238
In order to use it more generally,

59
00:02:55,278 --> 00:02:57,518
we'd give it a formal definition.

60
00:02:57,558 --> 00:03:00,358
What's permutation of multisets?

61
00:03:00,398 --> 00:03:02,518
For multiple elements

62
00:03:02,558 --> 00:03:06,438
r1 1's, r2 2's, ..., rt t's.

63
00:03:06,478 --> 00:03:09,438
The total number of elements is n.

64
00:03:09,478 --> 00:03:14,398
The permutation is denoted as P(n;r1,r2

65
00:03:14,438 --> 00:03:15,958
...,rt)

66
00:03:16,198 --> 00:03:20,958
It's equal to P(n,n) divided by

67
00:03:20,998 --> 00:03:24,758
(r1!×r2!×⋯×rt!)

68
00:03:24,798 --> 00:03:29,278
We could understand it as dividing the permutations of n

69
00:03:29,318 --> 00:03:32,398
by the arrangements of labels after labeling the repeated elements.

70
00:03:33,118 --> 00:03:35,358
Now let's rethink binomial theorem

71
00:03:35,398 --> 00:03:36,758
with it.

72
00:03:36,798 --> 00:03:39,198
Binomial theorem: a term in the

73
00:03:39,238 --> 00:03:43,038
expansion of (a+b)^n is

74
00:03:43,078 --> 00:03:46,398
a^k×b^(n-k).

75
00:03:46,518 --> 00:03:48,278
The coefficient of each term

76
00:03:48,318 --> 00:03:51,918
is actually equal to a permutation with repetitions

77
00:03:51,958 --> 00:03:56,278
in which there are k a's and (n-k) b's.

78
00:03:56,478 --> 00:03:59,958
Of course we could label all the k a's

79
00:03:59,998 --> 00:04:03,638
and all the (n-k) b's.

80
00:04:03,678 --> 00:04:06,158
According to the permutation of multisets we just studied,

81
00:04:06,198 --> 00:04:09,238
the coefficient of this term is equal to

82
00:04:09,278 --> 00:04:12,958
n! divided by k!

83
00:04:12,998 --> 00:04:16,238
and (n-k)!.

84
00:04:16,478 --> 00:04:18,558
So we just viewed the binomial theorem

85
00:04:18,598 --> 00:04:19,038
with another perspective.

86
00:04:19,078 --> 00:04:21,238
Could we extend the theorem

87
00:04:21,278 --> 00:04:25,958
to the exponentiation of more then two terms?

88
00:04:25,998 --> 00:04:28,918
Maybe we could deal with (a1+a2

89
00:04:28,958 --> 00:04:31,598
⋯at)^n.

90
00:04:31,718 --> 00:04:34,398
How would its coefficients be?

91
00:04:34,438 --> 00:04:38,198
A term of its expansion is a1^r1

92
00:04:38,238 --> 00:04:39,798
×a2^r2

93
00:04:39,838 --> 00:04:42,878
⋯×at^rt.

94
00:04:43,198 --> 00:04:46,478
The coefficient of this term

95
00:04:46,518 --> 00:04:49,838
is the number of arrangements of the

96
00:04:49,878 --> 00:04:54,598
permutation of r1 a1's, r2 a2's ...

97
00:04:54,998 --> 00:04:56,478
According to the calculation we just conducted,

98
00:04:56,518 --> 00:04:58,918
the permutation of n is n!.

99
00:04:58,958 --> 00:05:03,478
So it's n! divided by r1!

100
00:05:03,518 --> 00:05:06,038
×r2!×⋯×rt!

101
00:05:06,078 --> 00:05:09,198
Thus we could get the coefficient

102
00:05:09,238 --> 00:05:12,038
of a term in a polynomial expansion.

103
00:05:12,158 --> 00:05:14,598
Next, let's look at a game.

104
00:05:14,638 --> 00:05:15,358
This game

105
00:05:15,398 --> 00:05:17,118
is quite popular at game centers.

106
00:05:17,158 --> 00:05:19,838
Let's take ping pong balls as example.

107
00:05:19,878 --> 00:05:22,598
There are 6 tracks

108
00:05:22,638 --> 00:05:24,718
which are corresponding to 6 holes.

109
00:05:24,758 --> 00:05:25,398
Now

110
00:05:25,438 --> 00:05:27,278
we have 9 balls

111
00:05:27,318 --> 00:05:30,398
with labels 1...9.

112
00:05:30,438 --> 00:05:34,158
We'd send them into the 6 different

113
00:05:34,198 --> 00:05:36,318
holes via the corresponding tracks.

114
00:05:36,838 --> 00:05:38,718
If order matters, how many arrangements

115
00:05:38,758 --> 00:05:42,758
are there for the balls to go into the holes?

116
00:05:43,718 --> 00:05:45,638
This problem looks complex,

117
00:05:45,678 --> 00:05:47,758
it seems that there are a lot of situations.

118
00:05:47,838 --> 00:05:49,758
Let's analyze it.

119
00:05:49,798 --> 00:05:53,398
According to the order,

120
00:05:53,438 --> 00:05:56,478
the 9 balls are distributed into 6 areas.

121
00:05:57,358 --> 00:05:59,878
How should we represent these 6 areas?

122
00:05:59,918 --> 00:06:02,558
Actually we have a masterly method,

123
00:06:02,598 --> 00:06:03,638
with is called the bar method.

124
00:06:03,678 --> 00:06:06,438
To obtain 6 areas,

125
00:06:06,478 --> 00:06:10,038
we need 5 bars to

126
00:06:10,078 --> 00:06:11,918
partition it.

127
00:06:12,078 --> 00:06:15,118
So sending the 9 balls

128
00:06:15,158 --> 00:06:18,158
to the 6 areas in order

129
00:06:18,198 --> 00:06:19,198
is equal to

130
00:06:19,238 --> 00:06:20,918
that there are already 6 areas

131
00:06:20,958 --> 00:06:23,518
and we are going to fill 1,2,3,4...

132
00:06:23,558 --> 00:06:25,598
into these areas

133
00:06:25,758 --> 00:06:26,758
like this.

134
00:06:26,798 --> 00:06:29,038
This animation is an

135
00:06:29,078 --> 00:06:30,918
arrangement.

136
00:06:31,678 --> 00:06:35,398
So how should we denote such arrangements?

137
00:06:35,438 --> 00:06:38,638
Actually, the bars

138
00:06:38,918 --> 00:06:40,518
are the same,

139
00:06:41,078 --> 00:06:42,518
but all the other elements,

140
00:06:42,558 --> 00:06:45,198
which are number 1 ... 9, have no repetitions.

141
00:06:45,238 --> 00:06:46,838
It seems that in this permutation,

142
00:06:46,878 --> 00:06:48,518
there are both non-repeated elements

143
00:06:48,558 --> 00:06:50,398
and repetitions.

144
00:06:50,918 --> 00:06:53,518
We just learned in permutations of multisets that

145
00:06:53,558 --> 00:06:55,038
if there are repeated elements

146
00:06:55,078 --> 00:06:56,598
we have a good method

147
00:06:56,638 --> 00:06:59,878
which is to label the repeated elements and then

148
00:06:59,918 --> 00:07:02,918
divide the total number of permutations with the redundancy rate.

149
00:07:02,958 --> 00:07:04,318
It's the same here,

150
00:07:04,358 --> 00:07:06,038
although all the bars are the same,

151
00:07:06,078 --> 00:07:09,078
we could label them

152
00:07:09,118 --> 00:07:13,638
so we convert this problem into a permutation without repetitions.

153
00:07:13,958 --> 00:07:14,838
So now we find out that

154
00:07:14,878 --> 00:07:17,478
this problem is actually quite simple.

155
00:07:17,518 --> 00:07:21,638
At first there are

156
00:07:21,678 --> 00:07:25,398
5 bars and 9 numbers

157
00:07:25,438 --> 00:07:28,198
so there are a total of 14 different elements.

158
00:07:28,238 --> 00:07:31,998
They formed a permutation of 14, which is 14!.

159
00:07:32,038 --> 00:07:32,958
Then

160
00:07:32,998 --> 00:07:37,078
we need to divide it by the redundancy rates of labels.

161
00:07:37,118 --> 00:07:41,718
So the 14!/5!

162
00:07:41,758 --> 00:07:42,998
is the answer.

163
00:07:43,718 --> 00:07:46,718
It gives us a new idea

164
00:07:46,758 --> 00:07:49,198
that for some partition-related problems,

165
00:07:49,238 --> 00:07:51,958
we could use the bar method

166
00:07:51,998 --> 00:07:53,638
to find the answer easily.

167
00:07:54,358 --> 00:07:56,798
Some of you might not be familiar with this method,

168
00:07:56,838 --> 00:07:58,958
are there any other methods?

169
00:07:58,998 --> 00:08:02,878
We would also do the partition,

170
00:08:02,918 --> 00:08:05,078
and then we could try to analyze by steps

171
00:08:05,118 --> 00:08:07,638
to obtain the answer.

172
00:08:08,038 --> 00:08:10,918
As we already have 6 ares,

173
00:08:10,958 --> 00:08:14,518
how many choices are there for the first ball?

174
00:08:14,718 --> 00:08:17,638
It might be in area 1 ... area 6.

175
00:08:17,678 --> 00:08:19,918
There are 6 ways.

176
00:08:20,278 --> 00:08:22,478
After settling the first ball,

177
00:08:22,518 --> 00:08:24,238
let's see ..

178
00:08:24,278 --> 00:08:27,478
this is the situation for the second ball.

179
00:08:27,518 --> 00:08:29,958
How many areas are there now?

180
00:08:30,358 --> 00:08:33,678
Actually ball 1 partitioned an area

181
00:08:33,718 --> 00:08:34,998
into two.

182
00:08:35,038 --> 00:08:36,358
So for ball 2,

183
00:08:36,398 --> 00:08:38,118
it might be at the left of ball 1,

184
00:08:38,158 --> 00:08:40,438
or at the right of ball 1.

185
00:08:40,478 --> 00:08:42,558
So in this situation,

186
00:08:42,598 --> 00:08:44,998
there are more arrangements for ball 2,

187
00:08:45,038 --> 00:08:48,518
it could be sent to 7 different positions.

188
00:08:48,558 --> 00:08:49,918
So forth,

189
00:08:49,958 --> 00:08:52,558
after ball 1 and ball 2 are settled,

190
00:08:52,598 --> 00:08:55,078
there's one more choice for ball 3,

191
00:08:55,118 --> 00:08:56,638
there are 8 areas for it.

192
00:08:56,678 --> 00:08:59,798
So forth... until the last ball.

193
00:08:59,838 --> 00:09:01,038
How about the last ball?

194
00:09:01,078 --> 00:09:04,758
There are 14 choices for it.

195
00:09:04,798 --> 00:09:09,453
So the answer is to multiply from 6

196
00:09:09,573 --> 00:09:10,903
to 14.

197
00:09:11,023 --> 00:09:14,238
It's equal to 14!/5!,

198
00:09:14,278 --> 00:09:17,838
which is the same as what we got by the first method.

199
00:09:17,918 --> 00:09:20,356
So we've found that although the concept

200
00:09:20,396 --> 00:09:21,638
of permutation is simple

201
00:09:21,678 --> 00:09:24,358
there are a lot of skills.

202
00:09:24,398 --> 00:09:26,824
For problems with limitations of adjacency,

203
00:09:26,912 --> 00:09:29,118
we need to bind some elements together.

204
00:09:29,158 --> 00:09:30,678
For problems with multiple areas,

205
00:09:30,718 --> 00:09:33,158
we would usually use the bar method.

206
00:09:33,198 --> 00:09:36,278
Of course there are many other methods.

207
00:09:36,398 --> 00:09:37,177
Hopefully, after practicing,

208
00:09:37,222 --> 00:09:40,198
we could find more skillful methods.

209
00:09:40,238 --> 00:09:42,924
Next time we would introduce

210
00:09:43,003 --> 00:09:45,238
many more methods for combination.