I'm very glad to meet you again
to learn combinatorics.
In this week,
I'm going to introduce several basic counting principles.
Here we will explain
these counting principles with ping pong balls.
Table tennis is very popular in China.
The most important tournament in table tennis is the World Championships.
In this year (2014) it's held in Tokyo.
There's a trial before the World Championships.
which is held in Zhenjiang.
If we want to watch the trial in Zhenjiang,
How many routes are there from Beijing to Zhenjiang?
After a breif search,
we find that there are 7 high-speed trains
and 2 other trains.
So how many routes are there?
This is pretty simple.
There are a total 7+2=9 trains.
Someone might say
that she/he is busy and
she/he wants to go by aeroplane.
Unfortunately, there's no direct flight from Beijing to Zhenjiang.
So we need to fly to Nanjing at first,
and go to Zhenjiang by train.
If there are 5 flights in the morning
and there are 6 trains available
from Nanjing to Zhenjiang.
How many ways are there to go from Beijing to Zhenjiang
by aeroplane and train?
There are two phases here
and we are going to multiply them.
5×6=30 different ways.
Although the problems are simple,
they require different counting principles.
If we travel by train,
Actually, with different types of trains
we are counting by classification.
And we use addition.
If we travel by aeroplane,
we divide the journey into two segments,
and this time we need to use multiplication.
Thus the most fundamental counting principles
are actually based on the strategies of classification and segmentation.
They are addition principle and multiplication principle.
How should we describe addition principle
with mathematical languages?
At first let's describe it with events.
Event A can happen in m ways,
event B can happen in n ways.
By addition principle,
event A or B can happen
in m+n ways.
To describe it with the language of set theory.
The size of set A is m,
the size of set B is n.
If A intersected with B is empty,
the size of A unioned with B is M+N.
These are some mathematical formal languages,
Let's see a simple example.
There's a class
with 25 boys
and only 5 girls.
How many students are there in this class?
This is quite simple,
there are a total of 25+5=30 students.
The ratio of female students is relatively low,
so we might guess that this is a non-art class.
Now let's describe
multiplication principle with mathematical languages.
Multiplication principle also deals with
event A and event B.
But they happen consecutively in two steps.
A×B means that A and B happened in two steps.
Event A×B can happen in
m×n ways.
With the language of set theory,
the size of set A is m,
the size of set B is n.
Now we describe A×B with
ordered pairs.
In an ordered pair (a,b)
The first element a∈A,
the second element b∈B.
The size of A×B is
m×n.
This is multiplication principle.
Let's look at the non-art class again.
If they are going to elect a class committee.
They want to have a male monitor
and a female class leader.
How many possible combinations are there?
We could consider this problem by steps.
In the first step there are 25 ways to select the monitor.
In the second step there are 5 ways to select the class leader.
By multiplication principle,
there are a total of 25×5=125 ways.
We've known the addition principle and multiplication principle.
When applying them we need to
be cautious that
the events need to be independent.
For example,
in that non-art class,
there's something interesting.
Male student GFS
and female student BFM,
who are not
a couple as you might guess,
are siblings.
Now if we want to have a male monitor
and a female class leader.
we decide that they shouldn't be elected together.
This times how many arrangements are there?
We might count by classification,
let's consider whether GFS is elected as the monitor at first.
If he's elected,
the male monitor is decided
and there are only 4 candidates for the other position.
If GFS is not
elected as the monitor,
there are
24 ways for the monitor,
and 5 candidates for the class leader.
So when GFS is not elected,
we have 24×5 combinations.
By adding them together,
there are 4+24×5=124 combinations.
While the problem seems simple,
this solution is pretty complex.
Are there any simpler solutions?
Let's rethink the problem,
it's quite complex to analyze legal arrangements,
but there are only one
illegal arrangement.
So it would be much easier to subtract
illegal arrangements from the universal set.
There's only one illegal arrangement
and the total number of arrangements is 125.
Thus, 125-1=124
which is the same as what we just got.
So there's another counting principle
which is subtraction principle.
Sometimes we might
find something hard to calculate directly.
For instance,
This is a non-regular polygon.
It's not easy to calculate its area
directly.
A better method is to
add a small rectangle
at the corner
to make it a regular rectangle.
To calculate the area of the original polygon,
we only need to subtract the area of the small rectangle
from the area of the huge rectangle.
This is how subtraction principle works.
Similarly when we are counting we often
find that it's hard to count a set A
directly,
but set A might be included in a
universal set U.
Now we define the complement of A
to be a set such that it consists of
elements which ∈U
but not belongs to A.
We often use A-bar to represent the complement of A.
So we could count the elements in A
with the A-complement
when it's easier to count the complement set.
The size of A is equal to
the size of U minus the size of A-complement.
This is the subtraction principle.
Now we have addition, subtraction and multiplication principles.
But there's still one more
- division principle.
This one is very obvious and let's
take the non-art class as an example again.
There are 25 male students and 5 female students,
if we are going to partition the class into groups
such that each group contains one female student.
So if we are going to partition averagely,
how many male students are there in one group?
It's clear that
the answer is 25÷5=5.
These 4 counting principles
are the fundamentals.
Here we've introduced the basic counting principles
and next time we are going to introduce permutation and combination.