MTH00050 – Combinatorial Mathematics

Lecture 2: General counting methods for

arrangements and selections
Lecturer: Bùi Văn Thạch
TA: Lê Nhựt Nam, Trần Thị Thảo Nhi
Lab instructors: Lê Nhựt Nam, Trần Thị Thảo Nhi, Nguyễn Ngọc Toàn
{bvthach,lnnam,tttnhi,nntoan}@[Link]

1
Course topics
0. Introduction 6. Graphs

1. Set and counting 7. Tree problems

2. General counting methods for 8. Path problems

arrangements and selections 9. Network flows
3. Inclusion-exclusion principle and
Mobius inversion

4. Generating functions

5. Recurrence relations

3
Outline
1. Simple arrangements and selections

2. Arrangements and selections with repetitions

3. Distributions

4. Binomial identities

4
Simple arrangements and selections

Definition 2. A permutation of 𝑛 distinct objects is an arrangement,

or ordering, of the 𝑛 distinct.

5
Simple arrangements and selections

Definition 2. A permutation of 𝑛 distinct objects is an

arrangement, or ordering, of the 𝑛 distinct.

Definition 3. An 𝒓-permutation of 𝑛 distinct objects is an

arrangement using 𝑟 of the 𝑛 distinct.

6
Simple arrangements and selections

Definition 4. A 𝒓-combination of 𝑛 distinct objects is an unordered

selection, or subset, of 𝑟 out of the 𝑛 objects.

𝑛
We use 𝑃 𝑛, 𝑟 , 𝐶 𝑛, 𝑟 ≔ 𝐶𝑛𝑟 : = to denote the number of 𝑟 -
𝑟
permutations and 𝑟-combinations, respectively, of a set of 𝑛 objects.

7
Simple arrangements and selections

From the multiplication principle, we obtain

𝑃 𝑛, 2 = 𝑛 𝑛 − 1 ,
𝑃 𝑛, 3 = 𝑛 𝑛 − 1 𝑛 − 2 ,
𝑃 𝑛, 𝑛 = 𝑛 𝑛 − 1 𝑛 − 2 … 1 = 𝑛!

and

𝑛!
𝑃 𝑛, 𝑟 = 𝑛 𝑛 − 1 𝑛 − 2 … 𝑛 − 𝑟 − 1 =
𝑛−𝑟 !

8
Simple arrangements and selections

All 𝒓-permutations of 𝑛 objects can be generated by first picking any

𝑟-combination of the 𝑛 objects and the arranging these 𝑟 objects in any
order. Thus:
𝑃 𝑛, 𝑟 = 𝐶 𝑛, 𝑟 × 𝑃 𝑟, 𝑟 ,
and solving for 𝐶 𝑛, 𝑟 , we have:

𝑛 𝑃(𝑛, 𝑟) 𝑛!/ 𝑛 − 𝑟 ! 𝑛!
= 𝐶 𝑛, 𝑟 = = =
𝑟 𝑃(𝑟, 𝑟) 𝑟! 𝑟! 𝑛 − 𝑟 !

9
Example 12: Ranking Wizards

How many ways are there to rank

𝑛 candidates for the job of chief
wizard? If the ranking is made at
random (each ranking is equally
likely), what is the probability that
the fifth candidate, Gandalf, is in
second place?

10
Example 12: Ranking Wizards

Solution. A ranking is simply an arrangement, or permutation, of the 𝑛 candidates.

- For the 1st position, there are 𝑛 choices.
- For the 2nd position, there are 𝑛 − 1 choices.
- For the 3rd position, there are 𝑛 − 2 choices.
- And so on.
The total number of arrangements is:
𝑛 × 𝑛 − 1 × 𝑛 − 2 × ⋯ × 1 = 𝑛!
Thus, the number of ways to rank 𝑛 candidates is 𝑛! ways.

11
Example 12: Ranking Wizards

Solution. We need to find the probability that the fifth candidate, Gandalf, is ranked
in the second position when the ranking is made at random (each ranking is equally
likely):

Number of favorable outcomes

Prob(Gandalf second) = .
Total number of outcomes
As we know that the number of ways to rank 𝑛 candidates is 𝑛! ways. Now, we
need to count outcomes where Gandalf is ranked second.

Let 𝑛 candidates as 𝐶1 , 𝐶2 , … , 𝐶𝑛 where Gandalf is 𝐶5 .

12
Example 12: Ranking Wizards

Solution. To count the number of favorable rankings:

- Fix Gandalf in the second position
- Arrange the remaining candidates
So, the number of favorable outcomes (rankings where Gandalf is in second place)
is: 𝑛 − 1 !
Thus, the probability that Gandalf is in second place is:

𝑛−1 ! 1
Prob(Gandalf second) = = .
𝑛! 𝑛

13
Example 13: Arrangements with Repeated Letters

How many ways are there to arrange the seven letters in the word
SYSTEMS? In how many of these arrangements do the three Ss
appear consecutively?

14
Example 13: Arrangements with Repeated Letters

Solution. The word "SYSTEMS" has seven letters: S, Y, S, T, E, M, S where:

- The letter S appears 3 times.
- The letters Y, T, E, and M each appear 1 time.
We first pick the positions that the other four letters E, M, T, Y will occupy in the
seven-letter arrangement, and then the three Ss will fill the remaining three
positions in one way. There are seven possible positions for E, six for M, five for T,
and four for Y.
Thus, there are 𝑃 7, 4 = 7!Τ3! = 840 arrangements.

15
Example 13: Arrangements with Repeated Letters

To find the number of arrangements where the three S’s appear consecutively, we
can treat the three S’s as a single "super letter" or block. The word "SYSTEMS"
now consists of:

- 1 block of [SSS]

- The remaining letters: Y, T, E, M (each appearing once)

So, the problem reduces to arranging the five distinct letters, Y, T, E, M and SSS
(treated as a single letter), which can be done in 5! = 120 ways.

16
Example 14: Poker Probabilities

a) How many 5-card hands (subsets) can be

formed from a standard 52-card deck?

b) If a 5-card hand is chosen at random, what is

the probability of obtaining a flush (all five
cards in the hand are in the same suit)?

c) What is the probability of obtaining three, but

not four, Aces?

17
Example 14: Poker Probabilities

a) A 5-card hand is a subset of five cards chosen from the 52 cards in a deck, and
so there are:

52!
𝐶 52, 5 = = 2,598,960.
47! 5!

18
Example 14: Poker Probabilities

b) To find the probability of a flush, we need to find the

number of 5-card subsets with all cards of the same suit.
There are four suits, and a subset of five cards from the
13 cards in a given suit can be chosen in 𝐶 13, 5 =
13!Τ 5! 8! = 1287 ways. So there are 4 × 1287 = 5148
flushes. Thus, we have:

5148
Prob 5 − card hand is a flush = = 0.00198
2,598,960

19
Example 14: Poker Probabilities

c) To count the number of hands with exactly three Aces, we must pick three of the
four Aces – done in 𝐶 4,3 = 4 ways – and then fill out the hand with two card
chosen from the 48 non-Ace cards – done in 𝐶 48,2 = 1128 ways. So, there
are 4 × 1128 = 4512 hands with exactly three Aces. Finally, we get:

4512
Prob 5 − card hand has exactly three Aces = = 0.00174.
2,598,960

20
The Set Composition Principle

• Enumerate a set using the multiplication principle by multiplying the

number of ways to form a first part by the number of ways to form a
second part (for a given first part).

• The first and second parts must be disjoint—elements in the set

must be uniquely identifiable as belonging to either the first or
second part.

21
Example 13 (continued): Arrangements with Repetitions

How many arrangements of the seven letters in the word SYSTEMS

have the E occurring somewhere before the M? How many
arrangements have the E somewhere before the M and the three Ss
grouped consecutively?

22
Example 13 (continued): Arrangements with Repetitions

Solution. Count arrangements of the 7 letters (S, Y, S, T, E, M, S) where E

appears before M.

- Choose 2 positions for E and M: 𝐶 7, 2 = 21 ways.

- Place E in the earlier position, M in the later (1 way).

- Arrange Y, T in 2 of the 5 remaining positions: 𝑃 5,2 = 20 ways.

- Place 3 S’s in the 3 remaining position: 1 ways

Thus, the answer is: 21 × 1 × 20 × 1 = 420.

23
Example 13 (continued): Arrangements with Repetitions

Solution. Count arrangements where E is before M and the 3 S’s are

consecutive.
- Treat 3 S’s as one "super letter" [SSS], reducing to 5 units: Y, T, E,
M, [SSS].
- Choose 2 positions for E and M: 𝐶 5,2 = 10 ways.
- Place E in the earlier position, M in the later: 1 way
- Arrange Y, T, [SSS] in the 3 remaining positions: 3! = 6 ways.
Thus, the answer is: 10 × 1 × 6 = 60.

24
Example 15: Counting Defective Products

A manufacturing plant produces ovens. At the last stage, an inspector

marks the ovens A (acceptable) or U (unacceptable). How many
different sequences of 15 As and Us are possible in which the third U
appears as the twelfth letter in the sequence?

25
Example 15: Counting Defective Products

Solution. The sequence has 15 positions, and each position can be either A
or U. Without any constraints, the total number of possible sequences would
be 215 since there are 2 choices (A or U) for each of the 15 positions.

- If the third U appears at the twelfth letter in the sequence, then the
subsequence composed of the first 11 letters must have exactly two Us
(and nine As). So there are 𝐶 11, 2 = 55 possible sequences for the
first 11 letters.

26
Example 15: Counting Defective Products

- There is one way to pick the twelfth letter— it is specified to be U.

- The remaining three letters in the sequence can be either A or U, which is

23 = 8 ways.

All together, the number of sequences is:

55 × 1 × 8 = 440.

27
Example 16: Probability of Repeated Digits

What is the probability that a 4-digit campus telephone number has

one or more repeated digits?

Hint. There are 104 = 10,000 different 4-digit phone numbers, so we break the
problem into four different cases of repetitions:
a) All four digits are the same.
b) three digits are the same, the other is different.
c) two digits are the same, the other two digits are also the same (e.g., 2828).
d) two digits are the same, the other two digits are each different (e.g., 5105).

28
Outline
1. Simple arrangements and selections

2. Arrangements and selections with repetitions

3. Distributions

4. Binomial identities

29
Example 17: Arrangements of banana
How many arrangements are there of the six letters b, a, n, a, n, a?

A possible arrangement can be illustrated as:

n a b n a a

30
Example 17: Arrangements of banana
How many arrangements are there of the six letters b, a, n, a, n, a?

A possible arrangement can be illustrated as:

n a b n a a

⇒ The key is to focus on the subset of positions where the as go and the
subset of positions where the ns go.

31
 Example 17: Arrangements of banana

1 2 3 4 5 6

Solution.

6
- First choosing the subset of 3 positions in the arrangement where the as will go: = 20 ways.
3
3
- Then the subset of two positions (out of the remaining three) where the ns will go: = 3 ways.
2
1
- Finally, the last remaining position gets the b: = 1 way
1
6 3 1
Thus, we have: × × = 20 × 3 × 1 = 60 ways.
3 2 1
32
 Example 17: Arrangements of banana

1 2 3 4 5 6

Solution.

6!
= 60
3! 2! 1!

33
Theorem 1. If there are 𝑛 objects, with 𝑟1 of type 1, 𝑟2 of type 2, …, and
𝑟𝑚 of type 𝑚, where 𝑟1 + 𝑟2 + ⋯ + 𝑟𝑚 = 𝑛, then the number of
arrangements of these 𝑛 objects, denoted as 𝑃 𝑛; 𝑟1 , 𝑟2 , … , 𝑟𝑚 is

𝑛 𝑛 − 𝑟1 𝑛 − 𝑟1 − 𝑟2 − ⋯ 𝑟𝑚−1 𝑛!
𝑃 𝑛; 𝑟1 , 𝑟2 , … , 𝑟𝑚 = 𝑟 𝑟2 … 𝑟𝑚 = .
1 𝑟1 ! 𝑟2 ! … 𝑟𝑚!

34
Example 18: Ordering Hot Dogs

How many different ways are there to select six hot dogs from three
varieties of hot dog?

35
Example 18: Ordering Hot Dogs

Solution. Suppose the three varieties are classic, cheese and veggie. Let a
selection be written down on an order form in the following fashion:

classic cheese veggie

x xxxx x

Each x represents a hot dog. The request shown on the form above is one classic,
four cheese, and one veggie. Since the hot dog chef knows that the sequence of
dogs on the form is classic, cheese and veggie, the request can simply be written
as xxxxx|x| without column headings.

36
Example 18: Ordering Hot Dogs

We observe that:

- Any selection of r hot dogs will consist of some sequence of 𝑟 xs and two |s.

- Conversely, any sequence of 𝑟 xs and two |s represents a unique selection: the

xs before the first | count the number of classic dogs; the xs between the two |s
count cheese; and the final xs count veggie.

⇒ There is a one-to-one correspondence between orders and such sequences!.

37
Example 18: Ordering Hot Dogs

We observe that:

- Any selection of r hot dogs will consist of some sequence of 𝑟 xs and two |s.

- Conversely, any sequence of 𝑟 xs and two |s represents a unique selection: the

xs before the first | count the number of classic dogs; the xs between the two |s
count cheese; and the final xs count veggie.

⇒ There is a one-to-one correspondence between orders and such sequences!.

Counting the number of sequences of six xs and two |s is an arrangement-with-

8 2 8!
repetition problem whose answer is 𝑃 8; 6, 2 = = = 28
6 2 6!2!
38
Theorem 2. The number of selections with repetition of 𝑟 objects chosen from 𝑛
types of objects is:
𝑟+𝑛−1
.
𝑟

39
Example 19: Grouping Classes

Nine students, three from Ms. A’s class, three from Mr. B’s class, and three from
Ms. C’s class, have bought a block of nine seats for their school’s homecoming
game. If three seats are randomly selected for each class from the nine seats in a
row, what is the probability that the three A students, three B students, and three C
students will each get a block of three consecutive seats?

40
Example 19: Grouping Classes

Solution.

- The number of arrangements three As, three Bs, and three Cs in the row of nine
seats is: 𝑃 9; 3,3,3 = 9!Τ3! 3! 3! = 1680 ways.

- If the three students of each class are to sit together, then we want to count
outcomes that are arrangements of the three blocks, AAA, BBB, and CCC. Thus,
instead of nine letters, we really are working now with three composite letters.
There are 3! = 6 ways to arrange these three composite letters.

Thus, the probability that each class sits together is 6 ∕ 1680.

41
Example 20: Sequencing Genes (1/)

The genetic code of organisms is stored in

DNA molecules as a long string of four
nucleotides: A (adenine), C (cytosine), G
(guanine), and T (thymine). Short strings of
DNA can be “sequenced”—the sequence of
letters determined—by various modern
biotech methods.

42
Example 20: Sequencing Genes (2/)

Although the DNA sequence for a single gene

typically has hundreds or thousands of letters,
there exist special enzymes that will split a
long string into short fragments by breaking
the string immediately following each
appearance of a particular letter.

43
Example 20: Sequencing Genes (3/

Suppose a C-enzyme (which splits after each appearance of C) breaks

a 20-letter string into eight fragments, which are identified to be: AC,
AC, AAATC, C, C, C, TATA, TGGC. Note that each fragment, except
the last one on the string, must end with a C. How many different
strings could have given rise to this set of fragments?

44
Example 20: Sequencing Genes (4/)
• Since the fragment TATA does not end with a C, it must go at the end of the
string.
…..TATA
• The other seven fragments can occur in any order.
• These fragments consist of three Cs, two ACs, one AAATC, and one TGGC.
• Treat each fragment as a letter. Then we must arrange seven letters, three of
one type, two of a second type, and one each of two other types.
• There are 𝑃 7; 3, 2,1,1 = 420 possible arrangements of the fragments to form
a 20-letter string
45
Example 21: Sequences with Varying Repetitions

How many ways are there to form a sequence of 10 letters from four
as, four bs, four cs, and four ds if each letter must appear at least
twice?

46
Example 21: Sequences with Varying Repetitions

Remark. To apply Theorem 1 we need to know exactly how many as,

bs, cs, and ds will be in the arrangement. Thus we have to break this
problem into a set of subproblems:
- First category: Four appearances of one letter and two appearances
of each other letter.
- Second category: Three appearances of two letters and two
appearances of the other two letters.

47
Example 21: Sequences with Varying Repetitions

In the first category:

- There are four cases for choosing which letter occurs four times.

- To arrange four of one letter and two of the three others, we have:
𝑃 10; 4,2,2,2 = 18,900 ways.

48
Example 21: Sequences with Varying Repetitions

In the second category:

- For choosing which two of the four letters occur three times:
𝐶 4,2 = 6 cases.

- To arrange three of two letters and two of the two others, we have:
𝑃 10; 3,3,2,2 = 25,200 ways.

Thus, we have 4 × 𝑃 10; 4,2,2,2 + 6 × 𝑃 10; 3,3,2,2 ways.

49
Example 22: Selecting Doughnuts

How many ways are there to fill a box with a dozen doughnuts chosen
from five different varieties with the requirement that at least one
doughnut of each variety is picked?

Solution. Left as an exercise to the students.

50
Example 23: Selections with Lower and Upper Bounds

How many ways are there to pick a collection of exactly 10 balls from a
pile of red balls, blue balls, and purple balls if there must be at least
five red balls? If at most five red balls?

Solution. Left as an exercise to the students.

51
Example 24

• Trong quần thể có 𝑛 phần tử, có đúng 𝑠 phần tử dương tính. Biết rằng
mình có thể chọn ngẫu nhiên một số lượng phần tử trong quần thể. Sau
mỗi lần chọn thì bỏ những phần tử đã chọn vào lại quần thể. Tính số
lượng phần tử chọn tối thiểu và số lần chọn tối thiểu sao cho xác suất
chọn được một phần tử dương tính ít nhất là 1 − 𝜖, với 𝜖 > 0.

52
Example 24

• The following conditions characterize the hypergeometric distribution:

• The result of each draw (the elements of the population being sampled)
can be classified into one of two mutually exclusive categories (e.g.
Pass/Fail or Employed/Unemployed).

• The probability of a success changes on each draw, as each draw

decreases the population (sampling without replacement from a finite
population).

53
A random variable

Example 24
A random variable X follows the hypergeometric distribution if its probability mass function is given by

𝐾 𝑁−𝐾
𝑝𝑋 𝑘 = Pr 𝑋 = 𝑘 = 𝑘 𝑛−𝑘
𝑁
𝑛

where

N: is the population size,

K: is the number of success states in the population,

n: is the number of draws (i.e. quantity drawn in each trial),

k: is the number of observed successes.

54
Outline
1. Simple arrangements and selections

2. Arrangements and selections with repetitions

3. Distributions

4. Binomial identities

55
Distributions

• Generally, a distribution problem is equivalent to an arrangement or

selection problem with repetition.

• Specialized distribution problems must be broken up into subcases that

can be counted in terms of simple permutations and combinations (with
and without repetition)

56
Distributions

• Generally, a distribution problem is equivalent to an arrangement or

selection problem with repetition.
• Specialized distribution problems must be broken up into subcases that
can be counted in terms of simple permutations and combinations (with
and without repetition)
𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑜𝑛𝑠 𝑜𝑓 𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡 𝑜𝑏𝑗𝑒𝑐𝑡𝑠 ⟺ 𝑎𝑟𝑟𝑎𝑛𝑔𝑒𝑚𝑒𝑛𝑡𝑠
and
𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑜𝑛𝑠 𝑜𝑓 𝑖𝑑𝑒𝑛𝑡𝑖𝑐𝑎𝑙 𝑜𝑏𝑗𝑒𝑐𝑡𝑠 ⟺ 𝑠𝑒𝑙𝑒𝑐𝑡𝑖𝑜𝑛𝑠

57
Basic Models for Distributions

Distinct Objects. The process of distributing 𝑟 distinct objects into 𝑛 different boxes
is equivalent to putting the distinct objects in a row and stamping one of the 𝑛
different box names on each object. Thus, there are
𝑛 × 𝑛 × ⋯ × 𝑛 𝑟 𝑛𝑠 = 𝑛𝑟
distributions of the 𝑟 distinct objects.

58
Basic Models for Distributions

Distinct Objects. The process of distributing 𝑟 distinct objects into 𝑛 different boxes
is equivalent to putting the distinct objects in a row and stamping one of the 𝑛
different box names on each object. Thus, there are
𝑛 × 𝑛 × ⋯ × 𝑛 𝑟 𝑛𝑠 = 𝑛𝑟
distributions of the 𝑟 distinct objects.

𝑛 different boxes 𝑟 distinct objects

Red Red Blue Green 59

Specified amount in each box

If 𝑟𝑖 objects must go in box 𝑖, 1 ≤ 𝑖 ≤ 𝑛, then there are 𝑃 𝑟; 𝑟1 , 𝑟2 , … , 𝑟𝑛

distributions.

6 distinct objects

3 1 2 How many in each box?

6 6−3 6−3−1
= 𝑃(6; 3,1,2)
3 1 2
60
 Basic Models for Distributions

Identical Objects. The process of distributing 𝑟 identical objects into 𝑛 different

boxes is equivalent to choosing an (unordered) subset of 𝑟 box names with
repetition from among the 𝑛 choices of boxes. Thus, there are

𝑟+𝑛−1 𝑟+𝑛−1 !
=
𝑟 𝑟! 𝑛 − 1 !

distributions of the 𝑟 identical objects.

𝑟 identical objects
Red Red Blue Blue Green Green Green 61
Basic Models for Distributions

Example: 7 identical objects into 3 distinct boxes

Red Red Blue Blue Green Green Green

7 = 2 + 2 + 3

62
Example 24: Assigning Diplomats

How many ways are there to assign 100 different diplomats to five
different continents? How many ways if 20 diplomats must be assigned
to each continent?

63
Example 24: Assigning Diplomats

How many ways are there to assign 100 different diplomats to five
different continents? How many ways if 20 diplomats must be assigned
to each continent?

Solution. According to the model for distributions of distinct objects,

this assignment equals the number of sequences of length 100
involving the five continental destination, 5100 .

64
Example 24: Assigning Diplomats

How many ways are there to assign 100 different diplomats to five
different continents? How many ways if 20 diplomats must be assigned
to each continent?

Solution. The constraint that 20 diplomats go to each continent means

that each continent name should appear 20 times in the sequence.
5
Thus, we have: 𝑃 100; 20, 20, 20, 20, 20 = 100! ∕ 20! ways.

65
Example 25: Bridge Hands

In bridge, the 52 cards of a standard card deck are randomly dealt 13

apiece to players North, East, South, and West. What is the probability
that West has all 13 spades? That each player has one Ace?

66
Example 25: Bridge Hands

In bridge, the 52 cards of a standard card deck are randomly dealt 13

apiece to players North, East, South, and West. What is the probability
that West has all 13 spades? That each player has one Ace?
Solution.
- Count the ways West can get all spades: 1 way.
- Count the ways to distribute the 52 − 13 = 39 non-spade cards
among the 3 other hands: 𝑃(39; 13, 13, 13) ways

67
Example 25: Bridge Hands

In bridge, the 52 cards of a standard card deck are randomly dealt 13

apiece to players North, East, South, and West. What is the probability
that West has all 13 spades? That each player has one Ace?

Solution. So, the probability what West has all the spades is:

39! 52! 52! 52

3
൘ 4
= 1 ൘ = 1 ൗ .
13! 13! 13! 39! 13

68
Example 25: Bridge Hands

In bridge, the 52 cards of a standard card deck are randomly dealt 13

apiece to players North, East, South, and West. What is the probability
that West has all 13 spades? That each player has one Ace?
Solution.
- First distribute the Aces: 4! ways.
4
- Then, distribute the 48 non-Aces: 𝑃 48; 12,12,12,12 = 48! ∕ 12!
ways.

69
Example 25: Bridge Hands

In bridge, the 52 cards of a standard card deck are randomly dealt 13

apiece to players North, East, South, and West. What is the probability
that West has all 13 spades? That each player has one Ace?
Solution. So, the probability that each player gets an Ace is:

4
4! 𝑃 48; 12,12,12,12 4! 48! 52! 13! 4! 48! 4 ൗ 52
= 4
൘ 4
= 4
× = 13
𝑃(52; 13,13,13,13) 12! 13! 12! 52! 4
= 0.105

70
Example 26: Distributing Candy

How many ways are there to distribute 20 (identical) sticks of red

licorice and 15 (identical) sticks of black licorice among five children?

71
Example 26: Distributing Candy

How many ways are there to distribute 20 (identical) sticks of red

licorice and 15 (identical) sticks of black licorice among five children?

Solution. Left as an exercise to the students.

72
Example 27: Distributing Balls

Show that the number of ways to distribute 𝑟 identical balls into 𝑛

distinct boxes with at least on ball in each is 𝐶(𝑟 − 1, 𝑛 − 1). With at
least 𝑟1 balls in the first box, at least 𝑟2 balls in the second box, …, and
at least 𝑟𝑛 balls in the 𝑛-th box, the number is 𝐶(𝑟 − 𝑟1 − 𝑟2 − ⋯ − 𝑟𝑛 +
𝑛 − 1, 𝑛 − 1).

73
Example 27: Distributing Balls

Solution.

- First put one ball in each of the r boxes.

- Then count the ways to distribute without restriction the remaining

𝑟 − 𝑛 balls into the 𝑛 boxes:

𝑟−𝑛 +𝑛−1 !
𝐶 𝑟 − 𝑛 + 𝑛 − 1, 𝑟 − 𝑛 = = 𝐶(𝑟 − 1, 𝑛 − 1)
𝑟−𝑛 ! 𝑛−1 !

74
Example 27: Distributing Balls

Solution.
- First, for each 𝐼, put 𝑟𝑖 balls in the 𝑖-th box.
- There are now 𝑟 − 𝑟1 − 𝑟2 − ⋯ − 𝑟𝑛 balls left.
- Finally, count the ways to distribute without restriction the remaining 𝑟 −
𝑟1 − 𝑟2 − ⋯ − 𝑟𝑛 balls into the 𝑛 boxes.
- So this can be done in
𝐶( 𝑟 − 𝑟1 − 𝑟2 − ⋯ − 𝑟𝑛 + 𝑛 − 1, 𝑟 − 𝑟1 − 𝑟2 − ⋯ − 𝑟𝑛
= 𝐶( 𝑟 − 𝑟1 − 𝑟2 − ⋯ − 𝑟𝑛 + 𝑛 − 1, 𝑛 − 1)

75
Example 28: Integer Solutions

How many non-negative integer solutions are there to the equation

𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 12

with:

a) 𝑥𝑖 ≥ 0?
b) 𝑥𝑖 ≥ 1?
c) 𝑥1 ≥ 2, 𝑥2 ≥ 2, 𝑥3 ≥ 4, 𝑥4 ≥ 0?

76
Example 28: Integer Solutions

Solution.

a) 𝑥𝑖 ≥ 0
An example of one solution is: 𝑥1 = 2, 𝑥2 = 3, 𝑥3 = 3, 𝑥4 = 4.

Two ways to think about this:

1. Let 𝑥𝑖 be the number of (identical) objects in box 𝑖, or

2. Let 𝑥𝑖 be the number of objects of type 𝑖 chosen.

The number of integer solutions is: 𝐶 12 + 4 − 1,12 = 455 ways.

77
Example 28: Integer Solutions

b) 𝑥𝑖 ≥ 1?
There are: 𝐶 12 − 4 + 4 − 1 , 4 − 1 = 𝐶 8 + 4 − 1,4 − 1 = 165 ways.

c) 𝑥1 ≥ 2, 𝑥2 ≥ 2, 𝑥3 ≥ 4, 𝑥4 ≥ 0?
There are: 𝐶 12 − 2 + 2 + 4 + (4 − 1), 4 − 1 = 𝐶 4 + 4 − 1,4 − 1 = 35
ways.

78
Equivalent forms for selection with repetition

Equivalent Forms for Selection with Repetition.

1. The number of ways to select 𝑟 objects with repetition from 𝑛 different

types of objects.

2. The number of ways to distribute 𝑟 identical objects into 𝑛 distinct boxes.

3. The number of nonnegative integer solutions

𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛 = 𝑟.

79
Example 28: Ingredients for a Witch’s Brew

A warlock goes to a store with $5 to buy ingredients for his wife’s

Witch’s Brew. The store sells bat tails for 25c/ apiece, lizard claws for
25c/ apiece, newt eyes for 25c/ apiece, and calf blood for $1 a pint
bottle. How many different purchases (subsets) of ingredients will $5
buy?

Solution. Left as an exercise to the students.

80
Example 29: Binary Patterns

What fraction of binary sequences of length 10 consists of a (positive)

number of 1s, followed by a number of 0s, followed by a number of 1s,
followed by a number of 0s? An example of such a sequence is
1110111000

Solution. Left as an exercise to the students.

81
Summarization

Ways to Arrange, Select, or Distribute 𝒓 Objects from 𝒏 Items or into 𝒏 Boxes

Arrangement (Ordered Combination (Unordered

Outcome) or Distribution Outcome) or Distribution
of Distinct Objects of Identical Objects

No repetition 𝑃(𝑛, 𝑟) 𝐶(𝑛, 𝑟)

Unlimited repetition 𝑛𝑟 𝐶(𝑛 + 𝑟 − 1, 𝑟)
Restricted repetition 𝑃 𝑛; 𝑟1 , 𝑟2 , … , 𝑟𝑚
82
Outline
1. Simple arrangements and selections

2. Arrangements and selections with repetitions

3. Distributions

4. Binomial identities

83
Table of binomial coefficients

- Compute a table of binomial coefficients using

𝑛 𝑛!
= .
𝑘 𝑘! 𝑛 − 𝑘 !

- We’ll look at several patterns. First, the nonzero entries of each row
are symmetric; e.g., row 𝑛 = 4 is

4 4 4 4 4
, , , , = 1,4,6,4,1
0 1 2 3 4
𝑛 𝑛
which reads the same in reverse. Conjecture: = .
𝑘 𝑛−𝑘 84
Table of binomial coefficients
𝑛 𝑘=0 𝑘=1 𝑘=2 𝑘=3 𝑘=4 𝑘=5 𝑘=6
𝑘
𝑘 =0 1 0 0 0 0 0 0
𝑘 =1 1 1 0 0 0 0 0
𝑘 =2 1 2 1 0 0 0 0
𝑘 =3 1 3 3 1 0 0 0
𝑘 =4 1 4 6 4 1 0 0
𝑘 =5 1 5 10 10 5 1 0
𝑘 =6 1 6 15 20 15 6 1

85
A binomial coefficient identity

Theorem 3. For non-negative integers 𝑘 ≤ 𝑛,

𝑛 𝑛 𝑛 𝑛
= , including = =1
𝑘 𝑛−𝑘 0 𝑛

86
A binomial coefficient identity

Theorem 3. For nonegative integers 𝑘 ≤ 𝑛,

𝑛 𝑛 𝑛 𝑛
= , including = =1
𝑘 𝑛−𝑘 0 𝑛

Proof.
𝑛 𝑛! 𝑛! 𝑛
= = = .
𝑘 𝑘! 𝑛 − 𝑘 ! 𝑛 − 𝑘 ! 𝑘! 𝑛 − 𝑘

87
Table of binomial coefficients
𝑛 𝑘=0 𝑘=1 𝑘=2 𝑘=3 𝑘=4 𝑘=5 𝑘=6 Total
𝑘
𝑘 =0 1 0 0 0 0 0 0 1
𝑘 =1 1 1 0 0 0 0 0 2
𝑘 =2 1 2 1 0 0 0 0 4
𝑘 =3 1 3 3 1 0 0 0 8
𝑘 =4 1 4 6 4 1 0 0 16
𝑘 =5 1 5 10 10 5 1 0 32
𝑘 =6 1 6 15 20 15 6 1 64

88
Sum of binomial coefficients

𝑛
Theorem 4. For integers 𝑛 ≥ 0, we have: σ𝑛𝑘=0 = 2𝑛
𝑘

89
Sum of binomial coefficients

𝑛
Theorem 4. For integers 𝑛 ≥ 0, we have: σ𝑛𝑘=0 = 2𝑛
𝑘

Proof. Based on the Binomial Theorem

𝑛
𝑛 𝑛 𝑘 𝑛−𝑘
𝑥+𝑦 =෍ 𝑥 𝑦 ,
𝑘
𝑘=0
plug in 𝑥 = 𝑦 = 1.

90
Recursion for binomial coefficients

• A recursion involves solving a problem in terms of smaller instances

of the same type of problem.
• Example: Consider 3-element subsets of [5]:
Subsets without 5 Subsets with 5
{1, 2, 3} {1, 2, 5}
{1, 2, 4} {1, 3, 5}
{1, 3, 4} {1, 4, 5}
{2, 3, 4} {2, 3, 5}
{2, 4, 5}
{3, 4, 5}
91
Recursion for binomial coefficients

Theorem 5. For nonnegative integers 𝑛, 𝑘:

𝑛+1 𝑛 𝑛
= +
𝑘+1 𝑘 𝑘+1

• The initial conditions are

𝑛 0
= 1, ∀𝑛 ≥ 0, = 0, ∀𝑘 ≥ 1
0 𝑘
𝑛
• For 𝑛 ≥ 0, the only 0-element subset of 𝑛 is ∅, so = 1.
0
0
• For 𝑘 ≥ 1, there are no 𝑘-element subset of 𝑛 = ∅, so =0
𝑘

92
Pascal’s triangle (Alternate way to present the table of binomial coefficients)

93
Pascal’s triangle (Alternate way to present the table of binomial coefficients)

• Initial conditions: Each row starts

𝑛 𝑛
with = 1 and ends with = 1.
0 𝑛
• Recursion: For the rest, each entry
is the sum of the two numbers it’s in-
between on the row above. E.g. 6 +
4 = 10.

94
Diagonal sums

• Form a diagonal from a 1

on the right edge, in
direction as shown, for
any number of cells, and
then turn for one cell.

95
Diagonal sums

• Yellow: 1 + 2 + 3 + 4 = 10

1 2 3 5 5
+ + + =
1 1 1 1 2
• Pink: 1 + 4 + 10 = 15

3 4 5 6
+ + =
3 3 3 4

96
Diagonal sums

We formal a pattern:

𝑘 𝑘+1 𝑘+2
+ +
𝑘 𝑘 𝑘
𝑛 𝑛+1
+ ⋯+ =
𝑘 𝑘+1

97
Diagonal sums

Theorem 6. For integers 0 ≤ 𝑘 ≤ 𝑛:

𝑘 𝑘+1 𝑘+2 𝑛 𝑛+1

+ + + ⋯+ =
𝑘 𝑘 𝑘 𝑘 𝑘+1

98
Diagonal sums

Theorem 6. For integers 0 ≤ 𝑘 ≤ 𝑛:

𝑘 𝑘+1 𝑘+2 𝑛 𝑛+1

+ + + ⋯+ =
𝑘 𝑘 𝑘 𝑘 𝑘+1

Proof. Prove by counting (𝑘 + 1)-element subsets of [𝑛 + 1] in two ways.

𝑛+1
- First way: The number of such subsets is
𝑘+1
- Second way: Categorize subsets by their largest element. (Left as home
exercise).

99
 𝑛
Special cases of 1 + 𝑥

Theorem 7.

𝑛 𝑛 𝑛 𝑛 2 𝑛 𝑘 𝑛 𝑛
1+𝑥 = + 𝑥+ 𝑥 +⋯+ 𝑥 + ⋯+ 𝑥
0 1 2 𝑘 𝑛

𝑛 𝑛
𝑛 𝑘 𝑛−𝑘 𝑛 𝑘
= ෍ 𝑥 1 =෍ 𝑥
𝑘 𝑘
𝑘=0 𝑘=0

100
 𝑛
Special cases of 1 + 𝑥

We will give combinatorial interpretations of these special cases:

For 𝑛 ≥ 0,
𝑛
𝑛
2𝑛 = 1+1 𝑛 =෍
𝑘
𝑘=0
For 𝑛 ≥ 0,
𝑛
𝑛 𝑛 𝑛 𝑘
0 = −1 + 1 =෍ −1
𝑘
𝑘=0
For 𝑛 ≥ 0,
𝑛
𝑛 𝑘
3𝑛 = 2+1 𝑛
=෍ 2
𝑘
𝑘=0
101
Example 30

Show that:
𝑛 𝑘 𝑛 𝑛−𝑚
=
𝑘 𝑚 𝑚 𝑘−𝑚

103
Example 30

Show that:
𝑛 𝑘 𝑛 𝑛−𝑚
=
𝑘 𝑚 𝑚 𝑘−𝑚
Solution. The left-hand side counts the ways to select a group of 𝑘 people
chosen from a set of 𝑛 people, and then to select a subset of 𝑚 leaders
within the group of 𝑘 people.

The right-hand side, first select the subset of 𝑚 leaders from the set of 𝑛
people and then select the remaining 𝑘 − 𝑚 members of the group from the
remaining 𝑛 − 𝑚 people. 104
Well-known binomial identities
𝑛 𝑛 𝑛 𝑛 (1)
+ + + ⋯+ = 2𝑛
0 1 2 𝑛

𝑛 𝑛+1 𝑛+2 𝑛+𝑟 𝑛+𝑟+1 (2)

+ + + ⋯+ =
0 1 2 𝑟 𝑟

𝑟 𝑟+1 𝑟+2 𝑛 𝑛+1 (3)

+ + + ⋯+ =
𝑟 𝑟 𝑟 𝑟 𝑟+1

𝑛 2 𝑛 2 𝑛 2 𝑛 2 2𝑛 (4)
+ + + ⋯+ =
0 1 2 𝑛 𝑛

105
Well-known binomial identities
𝑚
𝑚 𝑛 𝑚+𝑛 (5)
෍ =
𝑘 𝑟−𝑘 𝑟
𝑘=0

𝑚
𝑚 𝑛 𝑚+𝑛 (6)
෍ =
𝑘 𝑟+𝑘 𝑚+𝑟
𝑘=0
𝑚
(7)
𝑚−𝑘 𝑛+𝑘 𝑚+𝑛+1
෍ =
𝑘 𝑠 𝑟+𝑠+1
𝑘=0

106
Example 31

Evaluate the sum

1 × 2 × 3 + 2 × 3 × 4 + ⋯ 𝑛 − 2 𝑛 − 1 𝑛.

107
Example 31

Evaluate the sum

1 × 2 × 3 + 2 × 3 × 4 + ⋯ 𝑛 − 2 𝑛 − 1 𝑛.

Solution. The general term in this sum:

𝑘!
𝑘−2 𝑘−2 𝑘 = = 𝑃 𝑘, 3 .
𝑘−3 !

108
Example 31

Furthermore, we have:

𝑘! 𝑃 𝑘, 3
𝐶 𝑘, 3 = = .
𝑘 − 3 ! 3! 3!

So, the given sum can be re-written as:

3 4 𝑛 3 4 𝑛 𝑛+1
3! + 3! + ⋯ + 3! = 3! + + ⋯+ = 3! .
3 3 3 3 3 3 4

109
Example 32

Evaluate the sum

12 + 22 + 32 + ⋯ + 𝑛 2 .

110
Example 32

Evaluate the sum

12 + 22 + 32 + ⋯ + 𝑛 2 .

Solution. In the general term of this sum, it can be written as:

𝑘 2 = 𝑘 𝑘 − 1 + 𝑘,

111
Example 32

So, the given sum can be written as:

[ 1 × 0 + 1)] + [ 2 × 1 + 2)] + [(3 × 2) + 3)] + ⋯ + [𝑛(𝑛 − 1) + 𝑛]
= 2 × 1 + 3 × 2 + ⋯+ 𝑛 𝑛 − 1 + 1 + 2 + 3 + ⋯+ 𝑛

2 3 𝑛 1 2 𝑛
= 2 +2 + ⋯+ 2 + + + ⋯+
2 2 2 1 1 1

𝑛+1 𝑛+1
=2 +
3 2

112
Q&A

114