Transcript 1. Basic Rules

Lecture 4 (part 1)
Combinatorics
Reading: Epp Chp 6
1
Outline
1. Basic Rules
a)
b)
c)
d)
Linear Series Rule
Multiplication Rule
Addition and Difference Rule
Inclusion-Exclusion Rule
2. Common Counting Scenarios
a) Permutations (Ordered Selections)
b) Combinations (Unordered Selections)
c) Counting ordered partitions / permutations of multi-sets
3. Algebra of Combinations
4. Binomial Theorem
2
1. Basic Rules
1.1 Linear Series Rule.
If m and n are integers such that m n, then
there are n-m+1 integers from m to n inclusive.
Example 1: How many integers are there in the
sequence 10, 11, 12, …, 19, 20?
Ans: 20 – 10 + 1 = 11
Example 2: How many integers are there in the
sequence -8,-7,-6,…-1,0,1,2,…4, 5?
Ans: 5 – (–8) + 1 = 14
3
1. Basic Rules
1.1 Linear Series Rule.
If m and n are integers such that m n, then
there are n-m+1 integers from m to n inclusive.
Example 3: How many integers are there in 0 to
1000 inclusive, that are divisible by 3.
The integers are 0,3,6,9,…,996,999, which are in
the form 3k, where k = 0,1,2,…,333.
Hence there are 333-0+1 = 334 integers from 0 to
1000 which are divisible by 3.
4
1. Basic Rules: Multiplication Rule
1.2 Multiplication Rule
If an operation consists of a sequence of steps/events E1,
E2 … Ek and if each Ei can be performed in ni ways
regardless of how the previous steps E1, … Ei-1 were
performed (i.e. independent), then the entire operation
can be performed in n1n2…nk ways.
Proof of multiplication rule is by induction
(Left as an exercise)
5
1. Basic Rules: Multiplication Rule
1.2 Multiplication Rule
If an operation consists of a sequence of steps/events E1,
E2 … Ek and if each Ei can be performed in ni ways
regardless of how the previous steps E1, … Ei-1 were
performed (i.e. independent), then the entire operation
can be performed in n1n2…nk ways.
Example 1:
At breakfast, you are given a choice of coffee or tea, and a choice
of a scrambled, fried and boiled egg. How many different kinds of
breakfast can you have?
Scrambled
Ans:
Step 1: Choose coffee or tea => 2 ways
Coffee
Fried
Boiled
Step 2: Choose how you would like your
egg to be done => 3 ways regardless of
the choice made in step 1.
Scrambled
Tea
Total number of ways = 2 x 3 = 6 ways (Mul. Rule)
Fried
Boiled
6
1. Basic Rules: Multiplication Rule
Example 2:
Let A and B be finite sets. If |A| = m and |B| = n, how many
elements are there in (i) A  B ? (ii) P(A)?
(i) The task of selecting pairs for A  B is reduced to the
following steps:
Step 1: Choose an element x from A : m ways.
Step 2: Choose an element y from B : n ways regardless
of choices made in step 1.
Total number of ways of performing the task
= total number of elements in A  B
= m  n (Multiplication Rule)
7
1. Basic Rules: Multiplication Rule
Example 2:
Let A and B be finite sets. If |A| = m and |B| = n, how many
elements are there in (i) A  B ? (ii) P(A)?
(ii) Let the elements of A be a1 , a2 , a3 ,…, am
The task of forming a subset of A is reduced to the following
procedure:
Step 1: Either take or drop element a1 : 2 ways.
Step 2: Either take or drop element a2 : 2 ways regardless of choices
made in step 1.
Step 3: Either take or drop element a3 : 2 ways regardless of choices
made in steps 1 and 2.
…
Step m: Either take or drop element am : 2 ways regardless of choices
made in steps 1, 2, 3, 4, …, m-1.
Total number of ways of performing the task (by multiplication
rule) = 2  2  2  …  2 = 2m
8
m times of 2
1. Basic Rules: Multiplication Rule
Example 3:
A car license plate has 3 letters of alphabet followed by 4
single digit numbers. How many different car licenses can be
issued (a) if repetitions of alphabets/numbers in the license
plate is allowed; (b) if repetitions are not allowed?
Ans (a):
The task of forming a license plate number consists of the
following sub-tasks:
Step 1: choose the 1st letter : 26 ways.
Step 2: choose the 2nd letter : 26 ways (independent of step 1).
Step 3: choose the 3rd letter : 26 ways (independent of steps 1-2).
Step 4: choose the 1st digit : 10 ways (independent of steps 1-3).
Step 5: choose the 2nd digit : 10 ways (independent of steps 1-4).
Step 6: choose the 3rd digit : 10 ways (independent of steps 1-5).
Step 7: choose the 4th digit : 10 ways (independent of steps 1-6).
Total number of performing the task = 263  104
9
1. Basic Rules: Multiplication Rule
Example 3:
A car license plate has 3 letters of alphabet followed by 4
single digit numbers. How many different car licenses can be
issued (a) if repetitions of alphabets/numbers in the license
plate is allowed; (b) if repetitions are not allowed?
Ans (b):
The task of forming a license plate number consists of the
following sub-tasks:
Step 1: choose the 1st letter : 26 ways.
Step 2: choose the 2nd letter : 25 ways (independent of step 1).
Step 3: choose the 3rd letter : 24 ways (independent of steps 1-2).
Step 4: choose the 1st digit : 10 ways (independent of steps 1-3).
Step 5: choose the 2nd digit : 9 ways (independent of steps 1-4).
Step 6: choose the 3rd digit : 8 ways (independent of steps 1-5).
Step 7: choose the 4th digit : 7 ways (independent of steps 1-6).
Total number of performing the task = 26  25  24  10  9  8  7
10
1. Basic Rules: Multiplication Rule
Example 4: (Limitations of the Multiplication Rule)
Two teams A and B are to play each other repeatedly until one
wins two games in a row, or until a total of 3 games. How many
ways can a tournament be played?

Incorrect answer:
Step 1: Either A wins or B wins : 2 ways.
Step 2: Either A wins or B wins : 2 ways.
Step 3: Either A wins or B wins : 2 ways.
dependent
dependent
Total number of ways = 2  2  2
11
1. Basic Rules: Multiplication Rule
Example 4: (Limitations of the Multiplication Rule)
Two teams A and B are to play each other repeatedly until one
wins two games in a row, or until a total of 3 games. How many
ways can a tournament be played?

The above example illustrates a situation when the
multiplication rule cannot be used.
A wins
A wins
B wins
B wins
A wins

B wins
A wins
A wins
B wins
B wins
This is because the subsequent events (games) are dependent
12
on the outcome of the previous events.
1. Basic Rules: Multiplication Rule
Example 5: (Goal Re-ordering is a possible way to by-pass
dependency of tasks)
Three officers – A president, a treasurer, and a secretary, are to
be chosen from among 4 people: A, B, C, D. Suppose that A
cannot be president, and either C or D must be secretary. How
many ways can the officers be chosen?
Incorrect answer:
Selecting three officers can be broken down to the following
tasks:
Step 1: Select the president : 3 ways.
dependent
Step 2: Select the treasurer : 3 ways.
dependent
Step 3: Select the secretary : 2 ways.
Total number of performing the task = 3  3  2 ways
13
1. Basic Rules: Multiplication Rule
Example 5: (Goal Re-ordering is a possible way to by-pass
dependency of tasks)
Three officers – A president, a treasurer, and a secretary, are to
be chosen from among 4 people: A, B, C, D. Suppose that A
cannot be president, and either C or D must be secretary. How
many ways can the officers be chosen?
Step 1: Select the
president: 3 ways
B
start
Step 2: Select the treasurer:
number of ways DEPENDENT
on the outcome of step 1!!!
C
A
C
D
D
D
C
A
D
B
D
A
C
B
C
C
D
Step 3: Select
the secretary:
number of ways
DEPENDENT on
the outcome of
step 2, which is
in turn,
DEPENDENT on
step 1.
14
1. Basic Rules: Multiplication Rule
Example 5: (Goal Re-ordering is a possible way to by-pass
dependency of tasks)
Three officers – A president, a treasurer, and a secretary, are to
be chosen from among 4 people: A, B, C, D. Suppose that A
cannot be president, and either C or D must be secretary. How
many ways can the officers be chosen?
Answer:
Independence of events can sometimes be restored through
the re-ordering of your tasks.
Step 1: Select the secretary : 2 ways (C or D).
Step 2: Select the president : 2 ways regardless of the choice
taken in step 1 (person B with the remaining person from step
1)
Step 3: Select the treasurer : 2 ways. (person A with the person
remaining from step 2)
Total number of performing the task = 2  2  2 ways
15
1. Basic Rules: Multiplication Rule
Example 5: (Goal Re-ordering is a possible way to by-pass
dependency of tasks)
Three officers – A president, a treasurer, and a secretary, are to
be chosen from among 4 people: A, B, C, D. Suppose that A
cannot be president, and either C or D must be secretary. How
many ways can the officers be chosen?
Step 1: Select the
secretary: 2 ways
Step 2: Select the
president: 2 ways
Step 3: Select the
treasurer: 2 ways
A
B
D
C
D
A
B
A
start
B
C
D
C
A
B
16
1. Basic Rules: Multiplication Rule
Summary:


Always check that the number of ways of each
step is independent of the choices of the
previous steps.
The multiplication rule did NOT say :
‘Each step is independent of the choices of previous step’.
It says :
‘The number of ways of each step is independent of the
choices of the previous step’

Get the subtle difference?
Goal re-ordering may help.
17
1. Basic Rules: Addition/Difference Rule
1.3 Addition Rule:
If a finite set A = A1 A2 An where all the Ai’s are
mutually disjoint, then |A| = |A1| + |A2| + + |An|
Difference Rule:
If A is a finite set and BA, then |A – B| = |A| – |B|
Addition Rule is proven by induction. (Proof are left as exercise).
Difference Rule is a corollary of the addition rule. (‘corollary’
meaning that ‘it is a result of’… meaning that you can prove/infer
the difference rule from the addition rule.)
Because when BA, (A – B) and B form a partition of A
(Meaning that (A – B) B = A and (A – B) B = )
Therefore by addition rule: |A – B| + |B| = |A|
And so: |A – B| = |A| – |B|
A
B
18
1. Basic Rules: Addition/Difference Rule
Example 1: A computer access code word consists of one
to three letters, chosen from the 26 alphabets, with
repetitions allowed. How many code words are
possible?
Answer:
 The set of all code words can be partitioned into subsets consisting
of those of length 1, length 2, and length 3.
Set of all code words of length 3
Set of all code
words of
length 1

Set of all code
words of
length 2
Set of all code
words of
length 3
By addition rule: |Set of all code words of length 3|
= | Set of all code words of length 1 |
+ | Set of all code words of length 2 |
+ | Set of all code words of length 3 |
19
1. Basic Rules: Addition/Difference Rule
Example 1: A computer access code word consists of one
to three letters, chosen from the 26 alphabets, with
repetitions allowed. How many code words are
possible?
Answer:
 The set of all code words can be partitioned into subsets consisting
of those of length 1, length 2, and length 3.
Set of all code words of length 3
Set of all code
words of
length 1




Set of all code
words of
length 2
Set of all code
words of
length 3
Number of code words of length 1 = 26
Number of code words of length 2 = 262 (Multiplication Rule)
Number of code words of length 3 = 263 (Multiplication Rule)
Total number of code words = 26 + 262 + 263 (Addition Rule)
20
1. Basic Rules: Addition/Difference Rule
Example 2: There are 15 different computer science books,
12 different math books, and 10 different chemistry
books on the shelf. How many ways can we select 2
books, each from a different subject?
Answer:
Set of selections of 2 books
1 book from
CS and 1
book Math

1 book from
CS and 1
book from
Chemistry
1 book from
Math and 1
book from
Chemistry
By addition rule: |Set of selections of 2 books|
= | Set of selection of 1 book from CS and 1 book from Math |
+ | Set of selection of 1 book from CS and 1 book from Chem |
+ | Set of selection of 1 book from Math and 1 book from Chem |21
1. Basic Rules: Addition/Difference Rule
Example 2: There are 15 different computer science boks,
12 different math books, and 10 different chemistry
books on the shelf. How many ways can we select 2
books, each from a different subject?
Answer:
Set of selections of 2 books
1 book from
CS and 1
book Math
1 book from
CS and 1
book from
Chemistry
1 book from
Math and 1
book from
Chemistry
15  12 +
15  10
+ 12  10
(M.R.)
(M.R.)
(M.R.)
Addition rule is reasoning-by-cases applied to counting!
22
1. Basic Rules: Addition/Difference Rule
Example 3: A group of eight people are attending the movies
together. If two of the eight people are enemies and do not
want to sit next to each other, how many ways can this group
sit in a row, such that the two enemies are separated?
Answer:
Different arrangements of 8 people in a row = 8! (by multiplicaton rule)
Different
arrangements
of 8 people in a
row where the 2
enemies sit
next to each
other
Different
arrangements
of 8 people in a
row where the 2
enemies sit
apart
How?
Step 1: Sit the 1st person: 8 ways
Step 2: Sit the 2nd person: 7 ways
regardless of outcome of step 1.
Step 3: Sit the 3rd person: 6 ways
regardless of outcome of step 1-2.
…
23
1. Basic Rules: Addition/Difference Rule
Example 3: A group of eight people are attending the movies
together. If two of the eight people are enemies and do not
want to sit next to each other, how many ways can this group
sit in a row, such that the two enemies are separated?
Answer:
Different arrangements of 8 people in a row = 8!
Different
arrangements
of 8 people in a
row where the 2
enemies sit
next to each
other
Different
arrangements
of 8 people in a
row where the 2
enemies sit
apart
= 27!
(by multiplicaton rule)
How?
Step 1: Sit the 2 enemies
together: 27 ways
Step 2-7: Sit the remaining 6
people: 654321
OR… Another way of looking at it:
Step 1: Combine the 2 enemies as 1 person and take it as an arrangement of 7
people to 7 chairs, (7!).
Step 2: Different ways of arranging the 2 enemies to sit side-by-side: 2 ways.
24
1. Basic Rules: Addition/Difference Rule
Example 3: A group of eight people are attending the movies
together. If two of the eight people are enemies and do not
want to sit next to each other, how many ways can this group
sit in a row, such that the two enemies are separated?
Answer:
Different arrangements of 8 people in a row = 8!
Different
arrangements
of 8 people in a
row where the 2
enemies sit
next to each
other
Different
arrangements
of 8 people in a
row where the 2
enemies sit
apart
= 27!
(by multiplicaton rule)
Answer = 8! – 27!
(Difference Rule)
25
1. Basic Rules: Addition/Difference Rule
Example 4: How many integers are there in 1000 to 9999 that
contain at least a digit 5.
Answer
= Number of integers in 1000 to 9999
– Number of integers in 1000 to 9999 that do not contain a digit 5.
(Difference Rule)
= (9999 – 1000 + 1) – 8.93
(Linear Series Rule) (Multiplication Rule)
= 2439
26
1. Basic Rules: Addition/Difference Rule
Example 5: How many 3 digit numbers have at least one digit
repeated?
Answer
= Number of 3 digit numbers
– Number of 3 digit numbers which have NO digit repeated
(Difference Rule)
(9 10 10)
(9 9 8)
Multiplication Rule:
Step 1: Choose hundreths digit
(must exclude leading ‘0’,
therefore only 9 ways)
Step 2: Choose tenths digit
Step 3: Choose units digit
Multiplication Rule:
Step 1: Choose hundreths digit
(must exlude leading ‘0’)
Step 2: Choose tenths digit
(10 ways, excluding the digit
in step 1. Therefore 9 ways)
Step 3: Choose units digit
27
1. Basic Rules: Inclusion-Exclusion Rule
1.4 Inclusion-Exclusion Rule:
 (For 2 sets) Given any sets A and B,
|A  B| = |A| + |B| – |A  B|
 (For 3 sets) Given any sets A, B and C,
|A  B  C | = |A| + |B| + |C| – |A  B| – |A  C| – |B  C|
+ |A  B  C|
 (For n sets) Given any sets A1 … An,
| A1  …  An |
=
| Ai |
i 1..n}
–
| Ai  Aj |
i,j 1..n}i,j distinct
+
| Ai  Aj  Ak |
i,j,k 1..n}i,j,k distinct
– …
28
1. Basic Rules: Inclusion-Exclusion Rule

Moral of the story behind the inclusionexclusion rule:
– If you over-count, then subtract away
those you counted more than once.
– If you under-count, then add back those
you have missed out.
This is applicable to any counting scenario.

Inclusion-Exclusion Rule is the
generalized version of the addition rule. If
the sets are disjoint, then the In-Ex rule
reduces to the addition rule.
29
1. Basic Rules: Inclusion-Exclusion Rule
Example 1: How many integers from 1 through 1000 are multiples
of 3 or 5? How many are neither multiples of 3 nor 5?
Answer:
|{Integers of multiples of 3 or 5}|
= |{Integers of multiples of 3}|
+ |{Integers of multiples of 5}|
– |{Integers of multiples of 3 and 5}|
(Inclusion-Exclusion Rule)
Multiples
of 3
Multiples
of 5
All integers
from 1 to 1000
30
1. Basic Rules: Inclusion-Exclusion Rule
Example 1: How many integers from 1 through 1000 are multiples
of 3 or 5? How many are neither multiples of 3 nor 5?
Answer:
|{Integers of multiples of 3 or 5}|
= |{Integers of multiples of 3}|
+ |{Integers of multiples of 5}|
– |{Integers of multiples of 3 and 5}|
(Inclusion-Exclusion Rule)
|{Integers of multiples of 3}| = |{3k | where k = 1,2,…333}| = 333
|{Integers of multiples of 5}| = |{5k | where k = 1,2,…200}| = 200
|{Integers of multiples of 3 and 5}| = |{15k | where k = 1,2,…66}| = 66
Ans = 333 + 200 – 66= 467
31
1. Basic Rules: Inclusion-Exclusion Rule
Example 1: How many integers from 1 through 1000 are multiples
of 3 or 5? How many are neither multiples of 3 nor 5?
Question: How many are neither multiples of 3 nor 5?
Answer:
{Int from 1..1000 with are multiples of 3 or 5}  {Int from 1..1000}
467
Ans = 1000-467 (By difference rule)
= 533
1000
32
1. Basic Rules: Inclusion-Exclusion Rule
Example 2: In a class of 50 students, 30 know Pascal, 18 know Fortran,
26 know COBOL, 9 know both Pascal and Fortran, 16 know Pascal
and COBOL, 8 know both Fortran and COBOL, 47 knows at least one
of the three languages.
(a) how many students know none of the three languages?
(b) how many students know all three languages?
(c) how many students know Pascal and Fortran but not COBOL?
(d) how many students know Pascal, but neither Fortran nor COBOL?
P = set of students who know Pascal; C = set of students who know COBOL
F = set of students who know Fortran; U = All 50 students.
(a) |U – (P C F)| = |U| – |(P C F)|
(By difference rule, since (P C F)  U)
|U|
= 50 (Given)
|(P C F)| = 47 (Given)
Therefore answer = 50-47 = 3.
33
1. Basic Rules: Inclusion-Exclusion Rule
Example 2: In a class of 50 students, 30 know Pascal, 18 know Fortran,
26 know COBOL, 9 know both Pascal and Fortran, 16 know Pascal
and COBOL, 8 know both Fortran and COBOL, 47 knows at least one
of the three languages.
(a) how many students know none of the three languages?
(b) how many students know all three languages?
(c) how many students know Pascal and Fortran but not COBOL?
(d) how many students know Pascal, but neither Fortran nor COBOL?
P = set of students who know Pascal; C = set of students who know COBOL
F = set of students who know Fortran; U = All 50 students.
(b) |(P C F)| = |P| + |C| + |F| – |PC| – |PF| – |CF| + |PCF|
(Inclusion-Exclusion Rule for 3 sets)
47 = 30 + 26 + 18 – 9 – 16 – 8 + |PCF|
|PCF| = 6
34
1. Basic Rules: Inclusion-Exclusion Rule
Example 2: In a class of 50 students, 30 know Pascal, 18 know Fortran,
26 know COBOL, 9 know both Pascal and Fortran, 16 know Pascal
and COBOL, 8 know both Fortran and COBOL, 47 knows at least one
of the three languages.
(a) how many students know none of the three languages?
(b) how many students know all three languages?
(c) how many students know Pascal and Fortran but not COBOL?
(d) how many students know Pascal, but neither Fortran nor COBOL?
P = set of students who know Pascal; C = set of students who know COBOL
F = set of students who know Fortran; U = All 50 students.
(c) |((PF) – (PFC))| = |PF| – |PFC|
=9–6=3
(Difference Rule)
P
C
6
9
F
35
1. Basic Rules: Inclusion-Exclusion Rule
Example 2: In a class of 50 students, 30 know Pascal, 18 know Fortran,
26 know COBOL, 9 know both Pascal and Fortran, 16 know Pascal
and COBOL, 8 know both Fortran and COBOL, 47 knows at least one
of the three languages.
(a) how many students know none of the three languages?
(b) how many students know all three languages?
(c) how many students know Pascal and Fortran but not COBOL?
(d) how many students know Pascal, but neither Fortran nor COBOL?
P = set of students who know Pascal; C = set of students who know COBOL
F = set of students who know Fortran; U = All 50 students.
(d) Similar to (c), those who know Pascal and COBOL, but not Fortran
= 16 – 6 = 10.
Since |P| = 30
By difference rule, those who know
Pascal, but neither fortran nor COBOL
= 30 – 19 = 11
P
30
C
? 10
6
3
F
36
Summary so far: Basic Counting Rules

Four basic Rules
–
–
–
–



Linear Series Rule
Multiplication Rule
Addition/Difference Rule
Inclusion-Exclusion Rule
All counting can be broken down to these four rules…
they may be likened to the ‘atoms’ of counting.
IMPT: Just like the logical inference rules, you use and
combine them together to create a proof, also here, you
have to combine the use of the counting rules when
necessary, to tackle the overall counting problem
We now use our ‘atoms’ to build common ‘procedural
calls’ to tackle common counting scenarios:
– Permutations
– Combinations
37

End of Lecture
38