0
00:00:13,480 --> 00:00:15,600
I'm very glad to meet you again

1
00:00:15,640 --> 00:00:17,720
to learn combinatorics.

2
00:00:17,760 --> 00:00:18,560
In this week,

3
00:00:18,600 --> 00:00:22,560
I'm going to introduce several basic counting principles.

4
00:00:22,600 --> 00:00:24,560
Here we will explain

5
00:00:24,600 --> 00:00:28,040
these counting principles with ping pong balls.

6
00:00:28,080 --> 00:00:30,840
Table tennis is very popular in China.

7
00:00:30,880 --> 00:00:33,680
The most important tournament in table tennis is the World Championships.

8
00:00:33,720 --> 00:00:35,960
In this year (2014) it's held in Tokyo.

9
00:00:36,000 --> 00:00:39,160
There's a trial before the World Championships.

10
00:00:39,200 --> 00:00:42,840
which is held in Zhenjiang.

11
00:00:42,880 --> 00:00:44,680
If we want to watch the trial in Zhenjiang,

12
00:00:44,720 --> 00:00:49,080
How many routes are there from Beijing to Zhenjiang?

13
00:00:49,240 --> 00:00:50,480
After a breif search,

14
00:00:50,520 --> 00:00:53,960
we find that there are 7 high-speed trains

15
00:00:54,000 --> 00:00:55,920
and 2 other trains.

16
00:00:55,960 --> 00:00:58,400
So how many routes are there?

17
00:00:58,440 --> 00:00:59,920
This is pretty simple.

18
00:00:59,960 --> 00:01:04,440
There are a total 7+2=9 trains.

19
00:01:04,680 --> 00:01:05,840
Someone might say

20
00:01:05,880 --> 00:01:07,560
that she/he is busy and

21
00:01:07,600 --> 00:01:09,600
she/he wants to go by aeroplane.

22
00:01:09,640 --> 00:01:12,080
Unfortunately, there's no direct flight from Beijing to Zhenjiang.

23
00:01:12,120 --> 00:01:13,960
So we need to fly to Nanjing at first,

24
00:01:14,000 --> 00:01:17,720
and go to Zhenjiang by train.

25
00:01:18,040 --> 00:01:20,520
If there are 5 flights in the morning

26
00:01:20,560 --> 00:01:22,160
and there are 6 trains available

27
00:01:22,200 --> 00:01:24,680
from Nanjing to Zhenjiang.

28
00:01:24,720 --> 00:01:27,920
How many ways are there to go from Beijing to Zhenjiang

29
00:01:27,960 --> 00:01:30,320
by aeroplane and train?

30
00:01:30,360 --> 00:01:32,400
There are two phases here

31
00:01:32,440 --> 00:01:35,320
and we are going to multiply them.

32
00:01:35,360 --> 00:01:38,480
5×6=30 different ways.

33
00:01:38,520 --> 00:01:40,640
Although the problems are simple,

34
00:01:40,680 --> 00:01:44,800
they require different counting principles.

35
00:01:44,840 --> 00:01:46,120
If we travel by train,

36
00:01:46,160 --> 00:01:48,120
Actually, with different types of trains

37
00:01:48,160 --> 00:01:50,520
we are counting by classification.

38
00:01:50,560 --> 00:01:52,360
And we use addition.

39
00:01:52,400 --> 00:01:53,680
If we travel by aeroplane,

40
00:01:53,720 --> 00:01:55,880
we divide the journey into two segments,

41
00:01:55,920 --> 00:01:59,720
and this time we need to use multiplication.

42
00:01:59,760 --> 00:02:02,720
Thus the most fundamental counting principles

43
00:02:02,760 --> 00:02:07,480
are actually based on the strategies of classification and segmentation.

44
00:02:07,520 --> 00:02:11,640
They are addition principle and multiplication principle.

45
00:02:12,000 --> 00:02:15,200
How should we describe addition principle

46
00:02:15,240 --> 00:02:17,520
with mathematical languages?

47
00:02:17,560 --> 00:02:20,560
At first let's describe it with events.

48
00:02:20,600 --> 00:02:24,320
Event A can happen in m ways,

49
00:02:24,360 --> 00:02:26,360
event B can happen in n ways.

50
00:02:26,400 --> 00:02:30,560
By addition principle,

51
00:02:30,600 --> 00:02:33,960
event A or B can happen

52
00:02:34,000 --> 00:02:36,240
in m+n ways.

53
00:02:36,280 --> 00:02:38,280
To describe it with the language of set theory.

54
00:02:38,320 --> 00:02:40,920
The size of set A is m,

55
00:02:40,960 --> 00:02:42,680
the size of set B is n.

56
00:02:42,720 --> 00:02:45,160
If A intersected with B is empty,

57
00:02:45,200 --> 00:02:50,160
the size of A unioned with B is M+N.

58
00:02:50,720 --> 00:02:52,360
These are some mathematical formal languages,

59
00:02:52,400 --> 00:02:54,320
Let's see a simple example.

60
00:02:54,360 --> 00:02:55,640
There's a class

61
00:02:55,680 --> 00:02:57,800
with 25 boys

62
00:02:57,840 --> 00:03:00,440
and only 5 girls.

63
00:03:00,480 --> 00:03:02,520
How many students are there in this class?

64
00:03:02,560 --> 00:03:04,480
This is quite simple,

65
00:03:04,520 --> 00:03:07,240
there are a total of 25+5=30 students.

66
00:03:07,280 --> 00:03:09,440
The ratio of female students is relatively low,

67
00:03:09,480 --> 00:03:13,240
so we might guess that this is a non-art class.

68
00:03:13,680 --> 00:03:15,680
Now let's describe

69
00:03:15,720 --> 00:03:20,320
multiplication principle with mathematical languages.

70
00:03:20,520 --> 00:03:23,520
Multiplication principle also deals with

71
00:03:23,560 --> 00:03:25,440
event A and event B.

72
00:03:25,480 --> 00:03:27,920
But they happen consecutively in two steps.

73
00:03:27,960 --> 00:03:32,800
A×B means that A and B happened in two steps.

74
00:03:32,840 --> 00:03:35,000
Event A×B can happen in

75
00:03:35,040 --> 00:03:37,480
m×n ways.

76
00:03:37,520 --> 00:03:39,480
With the language of set theory,

77
00:03:39,520 --> 00:03:41,760
the size of set A is m,

78
00:03:41,800 --> 00:03:43,920
the size of set B is n.

79
00:03:43,960 --> 00:03:47,320
Now we describe A×B with

80
00:03:47,360 --> 00:03:49,440
ordered pairs.

81
00:03:49,480 --> 00:03:52,320
In an ordered pair (a,b)

82
00:03:52,360 --> 00:03:55,120
The first element a∈A,

83
00:03:55,160 --> 00:03:57,160
the second element b∈B.

84
00:03:57,200 --> 00:04:01,520
The size of A×B is

85
00:04:01,560 --> 00:04:04,600
m×n.

86
00:04:04,640 --> 00:04:06,280
This is multiplication principle.

87
00:04:06,320 --> 00:04:08,720
Let's look at the non-art class again.

88
00:04:08,800 --> 00:04:11,960
If they are going to elect a class committee.

89
00:04:12,000 --> 00:04:15,120
They want to have a male monitor

90
00:04:15,160 --> 00:04:19,120
and a female class leader.

91
00:04:19,160 --> 00:04:22,920
How many possible combinations are there?

92
00:04:23,280 --> 00:04:26,120
We could consider this problem by steps.

93
00:04:26,160 --> 00:04:30,440
In the first step there are 25 ways to select the monitor.

94
00:04:30,480 --> 00:04:34,520
In the second step there are 5 ways to select the class leader.

95
00:04:34,560 --> 00:04:36,640
By multiplication principle,

96
00:04:36,680 --> 00:04:40,640
there are a total of 25×5=125 ways.

97
00:04:40,760 --> 00:04:43,880
We've known the addition principle and multiplication principle.

98
00:04:43,920 --> 00:04:46,400
When applying them we need to

99
00:04:46,440 --> 00:04:48,000
be cautious that

100
00:04:48,040 --> 00:04:51,600
the events need to be independent.

101
00:04:51,920 --> 00:04:53,040
For example,

102
00:04:53,080 --> 00:04:55,240
in that non-art class,

103
00:04:55,280 --> 00:04:57,680
there's something interesting.

104
00:04:57,720 --> 00:05:01,600
Male student GFS

105
00:05:01,640 --> 00:05:04,200
and female student BFM,

106
00:05:04,360 --> 00:05:05,680
who are not

107
00:05:05,720 --> 00:05:08,240
a couple as you might guess,

108
00:05:08,280 --> 00:05:10,280
are siblings.

109
00:05:10,320 --> 00:05:13,560
Now if we want to have a male monitor

110
00:05:13,600 --> 00:05:15,920
and a female class leader.

111
00:05:15,960 --> 00:05:20,800
we decide that they shouldn't be elected together.

112
00:05:20,920 --> 00:05:26,120
This times how many arrangements are there?

113
00:05:26,920 --> 00:05:29,760
We might count by classification,

114
00:05:29,800 --> 00:05:35,640
let's consider whether GFS is elected as the monitor at first.

115
00:05:35,680 --> 00:05:38,120
If he's elected,

116
00:05:38,160 --> 00:05:41,360
the male monitor is decided

117
00:05:41,400 --> 00:05:44,440
and there are only 4 candidates for the other position.

118
00:05:44,840 --> 00:05:46,120
If GFS is not

119
00:05:46,160 --> 00:05:49,960
elected as the monitor,

120
00:05:50,000 --> 00:05:51,320
there are

121
00:05:51,360 --> 00:05:53,560
24 ways for the monitor,

122
00:05:53,600 --> 00:05:56,280
and 5 candidates for the class leader.

123
00:05:56,320 --> 00:05:59,600
So when GFS is not elected,

124
00:05:59,640 --> 00:06:03,960
we have 24×5 combinations.

125
00:06:04,000 --> 00:06:06,640
By adding them together,

126
00:06:06,680 --> 00:06:11,520
there are 4+24×5=124 combinations.

127
00:06:11,680 --> 00:06:13,680
While the problem seems simple,

128
00:06:13,720 --> 00:06:16,720
this solution is pretty complex.

129
00:06:16,760 --> 00:06:19,160
Are there any simpler solutions?

130
00:06:19,200 --> 00:06:20,640
Let's rethink the problem,

131
00:06:20,680 --> 00:06:24,240
it's quite complex to analyze legal arrangements,

132
00:06:24,280 --> 00:06:26,600
but there are only one

133
00:06:26,640 --> 00:06:29,880
illegal arrangement.

134
00:06:30,440 --> 00:06:33,880
So it would be much easier to subtract

135
00:06:33,920 --> 00:06:37,120
illegal arrangements from the universal set.

136
00:06:37,160 --> 00:06:39,880
There's only one illegal arrangement

137
00:06:39,920 --> 00:06:43,320
and the total number of arrangements is 125.

138
00:06:43,360 --> 00:06:46,480
Thus, 125-1=124

139
00:06:46,520 --> 00:06:49,240
which is the same as what we just got.

140
00:06:49,280 --> 00:06:53,120
So there's another counting principle

141
00:06:53,160 --> 00:06:55,360
which is subtraction principle.

142
00:06:55,400 --> 00:06:58,120
Sometimes we might

143
00:06:58,160 --> 00:07:01,040
find something hard to calculate directly.

144
00:07:01,080 --> 00:07:02,240
For instance,

145
00:07:02,280 --> 00:07:05,640
This is a non-regular polygon.

146
00:07:05,680 --> 00:07:07,960
It's not easy to calculate its area

147
00:07:08,000 --> 00:07:09,400
directly.

148
00:07:09,440 --> 00:07:11,120
A better method is to

149
00:07:11,160 --> 00:07:13,560
add a small rectangle

150
00:07:13,600 --> 00:07:15,560
at the corner

151
00:07:15,600 --> 00:07:18,680
to make it a regular rectangle.

152
00:07:18,720 --> 00:07:20,960
To calculate the area of the original polygon,

153
00:07:21,000 --> 00:07:23,600
we only need to subtract the area of the small rectangle

154
00:07:23,640 --> 00:07:26,400
from the area of the huge rectangle.

155
00:07:26,440 --> 00:07:30,080
This is how subtraction principle works.

156
00:07:30,120 --> 00:07:32,360
Similarly when we are counting we often

157
00:07:32,400 --> 00:07:35,480
find that it's hard to count a set A

158
00:07:35,520 --> 00:07:37,040
directly,

159
00:07:37,080 --> 00:07:41,080
but set A might be included in a

160
00:07:41,120 --> 00:07:44,240
universal set U.

161
00:07:44,280 --> 00:07:47,720
Now we define the complement of A

162
00:07:47,760 --> 00:07:50,680
to be a set such that it consists of

163
00:07:50,720 --> 00:07:52,080
elements which ∈U

164
00:07:52,120 --> 00:07:55,080
but not belongs to A.

165
00:07:55,320 --> 00:08:00,400
We often use A-bar to represent the complement of A.

166
00:08:00,720 --> 00:08:02,520
So we could count the elements in A

167
00:08:02,560 --> 00:08:04,480
with the A-complement

168
00:08:04,520 --> 00:08:06,720
when it's easier to count the complement set.

169
00:08:06,760 --> 00:08:09,480
The size of A is equal to

170
00:08:09,520 --> 00:08:14,520
the size of U minus the size of A-complement.

171
00:08:14,680 --> 00:08:16,560
This is the subtraction principle.

172
00:08:16,880 --> 00:08:20,760
Now we have addition, subtraction and multiplication principles.

173
00:08:20,800 --> 00:08:23,080
But there's still one more

174
00:08:23,120 --> 00:08:24,520
- division principle.

175
00:08:24,560 --> 00:08:27,240
This one is very obvious and let's

176
00:08:27,280 --> 00:08:31,040
take the non-art class as an example again.

177
00:08:31,080 --> 00:08:35,400
There are 25 male students and 5 female students,

178
00:08:35,440 --> 00:08:36,840
if we are going to partition the class into groups

179
00:08:36,880 --> 00:08:39,200
such that each group contains one female student.

180
00:08:39,240 --> 00:08:42,680
So if we are going to partition averagely,

181
00:08:42,720 --> 00:08:44,480
how many male students are there in one group?

182
00:08:44,520 --> 00:08:45,520
It's clear that

183
00:08:45,560 --> 00:08:48,120
the answer is 25÷5=5.

184
00:08:48,160 --> 00:08:50,920
These 4 counting principles

185
00:08:50,960 --> 00:08:55,160
are the fundamentals.

186
00:08:55,200 --> 00:08:58,200
Here we've introduced the basic counting principles

187
00:08:58,240 --> 00:09:03,040
and next time we are going to introduce permutation and combination.