Transcript and 1

Lecture 4 (part 2)
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)
b)
c)
d)
Permutations (Ordered Selections)
Combinations (Unordered Selections)
Permutations with repetitions
Combinations with repetitions
3. Algebra of Combinations
4. Binomial Theorem
2
2.1 Permutations

Definition:
– An r-permutation of a set of n elements is
an ordered selection of r elements taken
from the set of n elements (1  r n).

Notation:
– The number of r-permutations of a set of n
elements is denoted as P(n,r).

Note: permutations are ordered
selections: selecting the object in the
first try/position, is considered different
from selecting that object in the second
or subsequent tries/positions.
3
2.1 Permutations

Theorem:
– If n and r are integers such that 1 r n, then
P(n,r) = n(n-1)(n-2)…(n-r+1)
or equivalently
Result:
Ordered
Tuple
P(n,r) = n! / (n-r)!

Proof:
– Uses the multiplication rule.
– Formal proof is by induction. Informal proof is as
follows:
{x1, x2 , x3 , … , xn}
1 r n
Step 1: n
choices
Step 2: n–1
choices
,
,
Position 1
Position 2
Step r : n–(r–1)
choices
,
Position r
Number of choices in step i is n-(i-1), regardless of the choices made in
previous steps => Can use Multiplication Rule: n(n-1)(n-2)…(n-r+1)
n!
n(n-1)(n-2)…(n-r+1)(n-r)(n-r-1)(n-r-1) …3.2.1
=
(n-r)!
(n-r)(n-r-1)(n-r-1) …3.2.1
4
2.1 Permutations

Theorem:
– If n and r are integers such that 1 r n, then
P(n,r) = n(n-1)(n-2)…(n-r+1)
or equivalently
P(n,r) = n! / (n-r)!

Corollary: P(n,n) = n! / (n-n)! = n!

Theorem: CIRCULAR PERMUTATIONS
– The number of ways of permuting r objects from a set of n
objects in a circle (in which two arrangements are the same
when one is a rotation of the other) is P(n,r) / r
– When n = r, we have P(n,n) / n = (n-1)!
5
2.1 Permutations
Example 1: (a) How many different ways can three of the
letters of the word BYTES be chosen and written in a
row? (b) How many different ways can this be done if the
first letter must be ‘B’
Answer:
(a) The problem is a 3-permutation from a set of 5 objects.
– P(5,3) = 5!/2! = 60
(b) 2 step process (Multiplication Rule)
– Step 1: Assign B to the first position: 1 way
– Step 2: Assign 4 letters to the remaining 2 positions:
P(4,2) ways, regardless of step 1.
– Answer = 1 x P(4,2) = 12.
6
2.1 Permutations
Example 2:
(a) In how many ways can the letters in the word
COMPUTER be arranged in a row?
(b) In how many ways can the letters in the word
COMPUTER be arranged in CO must appear together in
order?
Answer:
(a) P(8,8) = 8! (permutate all eight objects)
(b) P(7,7) = 7! (Treat CO as a unit)
7
2.1 Permutations
Example 3:
(a) How many ways can a group of 6 people be seated
around a table?
(b) How many ways can a group of 6 people be seated
around a table when two of them cannot sit next to each
other?
Answer:
(a) P(6,6)/6 = 5! (circular permutation)
(b) By difference rule:
Number of ways a group of 6 can sit around a table
– Number of ways in which the 2 enemies sit next
to each other
= 5! – (2xP(5,5)/5) (treat the 2 enemies as 1 person)
= 5! – (2x4!)
8
2.2 Combinations

Definition:
– An r-combination of a set of n elements is
a subset of r elements taken from the set
of n elements (r n).

Notation:
– The number of r-permutations of a set of n
elements is denoted as C(n,r), also as
n
r

Note: A combination is an unordered
selection: you are selecting a ‘set’, and
ordering is not important in sets.
9
2.2 Combinations

Theorem:
– If n and r are integers such that r n, then
C(n,r) = P(n,r) / r!
or equivalently
Result:
Ordered
Tuple
C(n,r) = n! / ( r!(n-r)! )

Informal Proof:
{x1, x2 , x3 , … , xn}
Step 1: Ordered
selection: P(n,r)
,
Position 1
,
,
Position 2
Position r
Step 2: Get rid of duplicates since
ordering is not important: P(n,r) / r!
,
,
Result: Set
,
10
2.2 Combinations
Example 1:
You are to select five members from a group of twelve to form a team.
(a) How many distinct five-person teams can be selected?
(b) If two of them insist on working together as a pair, such that any
team must either contain both of neither. How many five person
teams can be formed?
Answer:
(a) C(12,5)
(b) Use Addition Rule:
All 5-person teams satisfying the ‘2-friends’
constraint.
Set of twelve people
Set of five people
Those
teams
which
involve the
2 ‘friends’
Those
teams
which do
not involve
the 2
‘friends’
Step 1: select the two ‘friends’: 1 way
C(10,3)
Step 2: select the remaining 3 people: C(10,3)
+ C(10,5)
11
2.2 Combinations
Example 2:
You are to select five members from a group of twelve to form a team.
If two of them insist on working apart,how many five person teams
can be formed?
Answer: 1st version, using difference rule.
All 5-person teams
Those
teams with
the two
enemies
together
C(12,5)
Those
teams with
the two
enemies
apart
Step 1: select the two enemies: 1 way
C(10,3)
Step 2: select the remaining 3 people: C(10,3)
Ans: C(12,5) – C(10,3)
12
2.2 Combinations
Example 2:
You are to select five members from a group of twelve to form a team.
If two of them insist on working apart,how many five person teams
can be formed?
Answer: 2nd version, using addition rule.
All 5-person teams that do not contain the two enemies, say A and B
Those
teams
which
contain A
but not B
Those
teams
which
contain B
but not A
Those
teams
which do
not contain
A nor B
Step 1: select the A: 1 way
Step 2: select the
remaining people except
B: C(10,4)
C(10,4)
+ C(10,4)
+
C(10,5)
13
2.2 Combinations
Example 3:
A group of twelve consists of five men and seven women.
(a) How many five-person teams can be chosen that consists of three
men and two women?
(b) How many five-person teams contain at least one man?
(c) How many five-person teams contain at most one man?
(a) Answer:
Step 1: choose the men: C(5,3) ways
Step 2: choose the women: C(7,2) ways (regardless of the choices
made in step 1)
Multiplication rule: C(5,3) x C(7,2)
14
2.2 Combinations
Example 3:
A group of twelve consists of five men and seven women.
(a) How many five-person teams can be chosen that consists of three
men and two women?
(b) How many five-person teams contain at least one man?
(c) How many five-person teams contain at most one man?
(b) Answer:
Number of 5-person teams that contain at least one man
= Number of 5-person teams
– Number of 5-person teams that do not contain any men (all women).
(DIFFERENCE RULE)
= C(12,5) – C(7,5)
15
2.2 Combinations
Example 3:
A group of twelve consists of five men and seven women.
(a) How many five-person teams can be chosen that consists of three
men and two women?
(b) How many five-person teams contain at least one man?
(c) How many five-person teams contain at most one man?
(b) Answer:
Number of 5-person teams that contain at most one man
= Number of 5-person teams that contain no men
+ Number of 5-person teams that contain 1 man
(BY ADDITION RULE)
= (C(5,0) x C(7,5))
Step 1: Choose 0 men from 5 men
Step 2: Choose 5 women from 7 women
+ (C(5,1) x C(7,4))
Step 1: Choose 1 man from 5 men
Step 2: choose 4 women from 7 women
16
2.2 Combinations
Example 4:
10 people are to sit around two tables in a hawker (dealer) centre. The
first table has 6 chairs, the second table has 4 chairs.
(a) How many ways can this be done?
(b) How many ways can this be done if two of them needs to sit
together?
(a) Answer (version#1):
Step 1: Choose 6 people to sit on the first table
C(10,6)
Step 2: Arrange the 6 people on the first table
5! (Circular Permutation)
Step 3: Arrange the remaining 4 on the second table.
3! (Circular Permutation)
(BY MULTIPLICATION RULE)
= C(10,6) x 5! x 3!
= 10!/24
17
2.2 Combinations
Example 4:
10 people are to sit around two tables in a hawker centre. The first table
has 6 chairs, the second table has 4 chairs.
(a) How many ways can this be done?
(b) How many ways can this be done if two of them needs to sit
together?
(a) Answer (version#2):
Step 1: Permute 6 people from 10 circularly around the first table
P(10,6)/6
Step 2: Arrange the remaining 4 on the second table.
3! (Circular Permutation)
(BY MULTIPLICATION RULE)
= P(10,6)/6 x 3!
= 10!/24
18
2.2 Combinations
Example 4:
10 people are to sit around two tables in a hawker centre. The first table
has 6 chairs, the second table has 4 chairs.
(a) How many ways can this be done?
(b) How many ways can this be done if two of them needs to sit
together?
(b) Answer (version#1):
BY ADDITION RULE
Number of sitting arrangements where the two sit on the 1st table
BY MULTIPLICATION RULE
Step 1: Put the two on the first table: 1 way
Step 2: Select 4 more to join them: C(8,4)
Step 3: Permute them around the table : 5!
Step 4: Permute the remaining 4 circularly on 2nd table: 3!
+ Number of sitting arrangements where the two sit on the 2nd table
BY MULTIPLICATION RULE
Step 1: Put the two on the second table: 1 way
= (C(8,4)x5!x3!) +
Step 2: Select 2 more to join them: C(8,2)
(C(8,2)x3!x 5!)
19
Step 3: Permute them around the table: 3!
Step 4: Permute remaining 6 circularly on 1st table: 5!
2.2 Combinations
Example 4:
10 people are to sit around two tables in a hawker centre. The first table
has 6 chairs, the second table has 4 chairs.
(a) How many ways can this be done?
(b) How many ways can this be done if two of them needs to sit
together?
(b) Answer (version#2):
BY ADDITION RULE
Number of sitting arrangements where the two sit on the 1st table
BY MULTIPLICATION RULE
Step 1: Put the two on the first table: 1 way
Step 2: Permute 4 from 8 circularly on the 2nd table: P(8,4)/4
Step 3: Permute the 6 circularly on 1st table: 5!
+ Number of sitting arrangements where the two sit on the 2nd table
BY MULTIPLICATION RULE
Step 1: Put the two on the second table: 1 way
Step 2: Permute 6 from 8 circularly on the 1st table: P(8,6)/6
Step 3: Permute remaining 4 circularly on 2nd table: 3!
= (P(8,4)/4 x 5!) + (P(8,6)/6 x 3!)
20
2.3 Permutations with repetitions

Theorem (Permutations from a multi-set):
Given a collection of n objects of which:
– n1 are of type 1 and are indistinguishable from each other;
– n2 are of type 2 and are indistinguishable from each other;
…
– nk are of type k and are indistinguishable from each other;
and that n1 + n2 + … + nk = n, then the number of distinct
permutations of the n objects is
C(n, n1)  C(n – n1 , n2)  C(n – n1 – n2 , n3)  … 
C(n – n1 – n2 – … – nk-1 , nk)
or equivalently
n! / (n1!  n2!  …  nk! )
21
2.3 Permutations with repetitions
Example 1:
How many 8-bit strings have exactly three 1’s?
Answer (version#1 – details):
 Example:
– 10001101 is an 8-bit string, but has four 1’s
– 10010001 is an 8-bit string and has exactly three 1’s.

TECHNIQUE: Sometimes, you have to know (a) the set you are
choosing from; and (b) the destination ‘type’ that you are choosing to.
– Point of view#1: Choose from the set {0,1} and place into the bit
positions 1,2,3,4,5,6,7,8.
– Point of view#2: Choose from the bit positions 1,2,3,4,5,6,7,8, and
‘place’ them into the set {0,1} (i.e. assign them to either a bit 0 or 1)


Adopting different points of view of the same problem may help.
Use point of view#2:
– Step 1: Choose 3 bit positions from 8 to be assigned a bit 1: C(8,3)
– Step 2: Choose the remaining 5 bit positions for bit 0: C(5,5) = 1

Answer: C(8,3) (By multiplication rule)
22
2.3 Permutations with repetitions
Example 1:
How many 8-bit strings have exactly three 1’s?
Answer (version#2 – direct application of formula):
 What are the objects that you are permuting
– Point of view#1: 1’s and 0’s with duplicates?
– Point of view#2: the bit positions

Again, it is still using point of view#2.

Permute 8 objects (the bit positions)
– 3 of which are indistinguishable from each other
– 5 of which are indistinguishable from each other

Answer: 8!/(3! x 5!)
23
2.3 Permutations with repetitions
Example 2:
How many ways are there of ordering the letters of the word
MISSISSIPPI, which are distinguishable from each other?
Answer:
 What are the objects that you are permuting
– Point of view#1: The Letters M,I,S,P? (with duplicates?)
– Point of view#2: The 11 positions where the letters can be placed


Again, point of view#2.
Permute 11 objects (the letter positions)
– 4 of which are indistinguishable from each other (for the letter ‘S’)
– 4 of which (a different type) are indistinguishable from each other (for
the letter ‘I’)
– 2 of which (a different type) are indistinguishable from each other (for
the letter ‘P’)
– 1 position for letter ‘M’


Answer (use formula): 11!/(4! x 4! x 2! x 1!)
Answer (from scratch): C(11,4) x C(7,4) x C(3,2) x C(1,1)
24
2.4 Combinations with repetitions

Definition (r-combinations from a multi-set):
Given a set X of n objects, an r-combination with
repetition allowed (or r-combination with a multi-set of
size r) is an unordered selection of elements taken from
X with repetition allowed.

Theorem: The number of r-combination with repetition
allowed drawn from a set of n elements is C(r+n–1 , r).

Example: 3-combinations from a set {a,b,c,d}
–
–
–
–
–
–
–

[a,a,a]; [a,a,b]; [a,a,c]; [a,a,d]
[a,b,b]; [a,b,c]; [a,b,d];
[a,c,c]; [a,c,d]; [a,d,d];
[b,b,b]; [b,b,c]; [b,b,d];
[b,c,c]; [b,c,d]; [b,d,d];
[c,c,c]; [c,c,d]; [c,d,d];
[d,d,d]
Total Number = 20 = C(3+4-1 , 3)
25
2.4 Combinations with repetitions

Definition (r-combinations from a multi-set):
Given a set X of n objects, an r-combination with
repetition allowed (or r-combination with a multi-set of
size r) is an unordered selection of elements taken from
X with repetition allowed.

Theorem: The number of r-combination with repetition
allowed drawn from a set of n elements is C(r+n–1 , r).

Example: 3-combinations from a set {a,b,c,d}
Category a Category b Category c Category d
[a,a,a]
XXX
[a,a,b]
XX
X
[a,b,d]
X
X
[a,c,d]
X
[b,c,c]
X
X
X
X
XX
26
2.4 Combinations with repetitions

Definition (r-combinations from a multi-set):
Given a set X of n objects, an r-combination with
repetition allowed (or r-combination with a multi-set of
size r) is an unordered selection of elements taken from
X with repetition allowed.

Theorem: The number of r-combination with repetition
allowed drawn from a set of n elements is C(r+n–1 , r).

Example: 3-combinations from a set {a,b,c,d}
[a,a,a]
XXX
[a,a,b]
XX
X
[a,b,d]
X
X
[a,c,d]
X
[b,c,c]
X
X
X
X
XX
27
2.4 Combinations with repetitions

Definition (r-combinations from a multi-set):
Given a set X of n objects, an r-combination with
repetition allowed (or r-combination with a multi-set of
size r) is an unordered selection of elements taken from
X with repetition allowed.

Theorem: The number of r-combination with repetition
allowed drawn from a set of n elements is C(r+n–1 , r).

Example: 3-combinations from a set {a,b,c,d}
Problem generalized:
Selection
Represented by:
[a,a,a]
XXX|||
[a,a,b]
XX|X||
[a,b,d]
X|X||X
[a,c,d]
X||X|X
|X|XX|
[b,c,c]
• r-combination = putting r crosses
• From a set of n elements = putting
n-1 ‘|’s in between crosses.
Reduces to the same problem of
assigning 2-bits (X and |) to r+n-1
positions. (Permuting r+n-1
28
positions from a multi-set of {X,|}
2.4 Combinations with repetitions
Example 1: A person giving a party wants to set out 15 assorted cans of
soft drinks for his guests. He shops at a store that sells 5 different
types of soft drinks
(a) How many different selections of cans of 15 soft drinks can he
make?
(b) If root beer is one of the types of soft drinks, how many different
selections include at least 6 cans of root beer?
Answer:
(a) 15-combination (15 drinks) from a multi-set of 5 categories
– r = 15 drinks = 15 crosses
– n = 5 categories: need 4 ‘|’ to separate the crosses
– C(15+5-1 , 15) = C(19, 15) = 3876
(b) Step 1: take out 6 cans of root beer: 1 way
Step 2: select the remaining 9 cans: 9-combination (9 remaining
drinks) from a multi-set of 5 categories: C(9+5-1 , 9) = C(13,9) = 715
Final Answer = 1 x 715 = 715 (Multiplication Rule)
29
2.4 Combinations with repetitions
Example 2: How many solutions are there to the equation
x1 + x2 + x3 + x4 = 10
(a) if x1, x2, x3, x4 are non-negative integers?
(b) if x1, x2, x3, x4 are positive integers?
Answer:
(a) 10-combination from a multi-set of 4 categories
– r = 10 units = 10 crosses; to be distributed into…
– n = 4 categories: the four variables: need 3 ‘|’ to separate the crosses
– C(10+4-1 , 10) = C(13, 10) = 286
(b) Step 1: Assign 1 unit to each of the four variables: 1 way.
Step 2: Assign the remaining 6 units to the four variables:
6-combination from a multi-set of 4 categories
= C(6+4-1 , 6) = C(9,6) = 84
Final Answer = 1 x 84 = 84 (Multiplication Rule)
30
2.4 Combinations with repetitions
Example 3: How many triplets of the form (i,j,k) are there, when
(a) each i , j , k {1,…,n}
(b) each i , j , k {1,…,n} and 1 i  j  k n
Answer:
(a) Permutation: n3
(b) 3-combinations from a multi-set of n categories:
(Observation skills needed to relate problem to known scenario)
For example if 1 i  j  k 5, then we have 3-combinations from a
multi-set of 5 categories: 3 X’s and 4 ‘|’s
(1,1,2) being represented as XX|X|||
(1,2,4) being represented as X|X||X|
(2,3,5) being represented as |X|X||X
Therefore in general, answer is C(n+3-1 , 3)
= (n+2)!/ (3! x (n-1)!)
= (n+2)(n+1)n / 6
31
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)
b)
c)
d)
Permutations (Ordered Selections)
Combinations (Unordered Selections)
Permutations with repetitions
Combinations with repetitions
3. Algebra of Combinations
4. Binomial Theorem
32
3. Algebra of Combinations
Common properties
(1) C(n,r) = C(n, n-r)
(2) Pascal’s Formula: C(n+1, r) = C(n, r-1) + C(n,r)
Proof of (1)
 Proven Algebraically:
C(n,r) = n! / ( r!  (n-r)! ) = n! / ( (n-r)!  (n-(n- r))! ) = C(n, n-r)
 Proven using combinatorial reasoning (p331 of text)
Let A be a set with n elements.
Let the subsets of A of size r be B1, B2,…,Bk.
Each Bk can be paired up with a subset of A of size n–r:
namely A – Bk.
All subsets of size n
B1
B2
…
Bk
All subset of size n–r
A – B1
A – B2
…
A – Bk
33
3. Algebra of Combinations
Common properties
(1) C(n,r) = C(n, n-r)
(2) Pascal’s Formula: C(n+1, r) = C(n, r-1) + C(n,r)
Proof of (2): refer to p334 of recommended text.
 Implications: Pascal’s Triangle
0
0
1
0
2
1
3
0
4
0
1
1
2
1
3
1
4
1
1
1
2
2
3
2
4
2
1
3
3
4
3
1
4
4
1
1
2
3
4
1
3
6
1
4
134
4. Binomial Theorem



Binomial Theorem:
(a+b)n =
n
k=0
n
k
an-kbk
Algebraic proof is by induction on n. (p341 of text)
Combinatorial Proof:
(a+b)n = (a+b) (a+b) (a+b) … (a+b)
(n copies)
#1
b
a
#2
a
b
#3
a
a
…
…
#n
a
a
• What is the coefficient of an-kbk ?
• How many ways can we create the an-kbk term?
• Well, to create a term, we have to select either a or b from
each (a+b) group.
• Problem reduces to a n-permutation with repetitions
(previous section 2.3), of 2 types of objects: selecting n-k 35
copies of a and k copies of b: n!/(k!(n-k)!) = C(n,k)
4. Binomial Theorem

Binomial Theorem provides rapid
expansion of polynomials.
– Example 1: Expand (a+b)n.
C(5,0)a5b0 + C(5,1)a4b1 + C(5,2)a3b2 + C(5,3)a2b3 +
C(5,4)a1b4 + C(5,5)a0b5
= a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5

It also allows you to access a particular
term without the need to expand the
entire polynomial
– Example 2: What is the coefficient of a9b6
in the expansion of (a+b)15?
• Ans: C(15,6)
36
4. Binomial Theorem

Corollary of Binomial Theorem:
2n = (1+1)n
n
=
k=0
n
=
=
k=0
n
0
n
k
1n-k1k
(by binomial thm)
n
k
+
n
1
+
n
2
+ +
n
n
Q: If |S| = n, what is |P(S)|?
A: By addition rule:
number of subsets of size 0
+ number of subsets of size 1
37
+ number of subsets of size 2 + … + number of subsets of size n

End of Lecture
38