Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficients  
MATH/STAT 394: Probability I  
Arman Jahangiri  
University of Washington Department of Mathematics  
Summer 2026  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026  
1
 
Learning Goals  
By the end of this lecture, students should be able to:  
▶ apply the multiplication rule for counting;  
▶ distinguish between sampling with and without replacement;  
▶ compute permutations and ordered selections;  
▶ compute combinations and unordered selections;  
▶ understand the binomial coefficient combinatorially;  
▶ recognize and avoid overcounting;  
▶ prove combinatorial identities using counting arguments.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026  
2
The Multiplication Rule (Product Rule)  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026  
3
The Basic Counting Principle  
Multiplication Rule  
Suppose a procedure consists of two stages.  
▶ Stage 1 can be done in a ways;  
▶ for each choice in Stage 1, Stage 2 can be done in b ways.  
Then the entire procedure can be done in  
a × b  
ways.  
More generally, if a process has stages with  
n1, n2, . . . , nk  
possible choices respectively, then the total number of outcomes is n1n2 · · · nk .  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026  
4
Tree Interpretation  
The multiplication rule can be visualized using a tree.  
Suppose:  
▶ there are 3 choices for the first step;  
▶ each leads to 2 choices for the second step.  
Then, according to the Multiplication Rule, there are 3 × 2 = 6 possible outcomes.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026  
5
Example: License Plates  
Suppose a license plate consists of 3 letters, followed by 4 digits. Assume repetition is allowed.  
Figure: WA license plate. Source: Wikipedia.  
Choices:  
26 possibilities for each letter,  
10 possibilities for each digit.  
Thus the total number of possible license plates is  
(26 × 26 × 26) × (10 × 10 × 10 × 10) = 263 · 104 = 175, 760, 000 (?!)  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026  
6
Example: Binary Strings  
A binary string of length n consists only of 0’s and 1’s.  
Each position has:  
2 choices.  
Using the multiplication rule:  
= 2n.  
2
0 or 1  
2
2
×
× · · · ×  
0or1  
0or1  
| {z } | {z }  
| {z }  
position 1 position 2  
position n  
Therefore, Number of binary strings of length n is 2n.  
Remark: This is also equal to the number of all possible subsets of a set with n elements. (Why?)  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026  
7
Sampling With and Without Replacement  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026  
8
Ordered Sampling With Replacement  
Suppose we have a set of size n, and we perform k draws with replacement, where 1 ≤ k ≤ n.  
With replacement means: after each draw, the selected object is returned before the next draw.  
Therefore, each draw has exactly n possible choices.  
Using the multiplication rule:  
= nk .  
n
choices  
n
choices  
n
×
× · · · ×  
choices  
| {z }  
draw k  
| {z } | {z }  
draw 1  
draw 2  
Hence, the number of possible ways to draw k ordered items, with replacement, from a set of size n, is  
nk .  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026  
9
Example: PIN Codes  
A 4-digit PIN code uses digits 0–9.  
Digits may repeat.  
Each position has:  
Therefore:  
10 choices.  
104 = 10000  
possible PINs.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 10  
Ordered Sampling Without Replacement  
Now suppose selected objects are not returned after each draw.  
Then the number of available choices decreases after every selection.  
Using the multiplication rule:  
n
n − 1  
n − 2  
n − k + 1  
×
×
× · · · ×  
choices  
| {z }  
draw 1  
choices  
{z  
choices  
{z  
choices  
{z  
|
}
|
}
|
}
draw 2  
draw 3  
draw k  
n!  
= n(n − 1)(n − 2) · · · (n − k + 1) =  
.
(n − k)!  
Important  
Without replacement means that the choices depend on previous selections.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 11  
Example: Arranging Books  
Suppose 5 distinct books are arranged on a shelf.  
Choices:  
5 choices for the first position,  
4 for the second,  
3 for the third,  
etc.  
Therefore, the number of arrangements is  
5 · 4 · 3 · 2 · 1 = 5! = 120.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 12  
Factorials and Permutations  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 13  
Factorials  
Definition  
For a positive integer n,  
n! = n(n − 1)(n − 2) · · · 2 · 1.  
Also define  
Examples:  
0! = 1.  
1! = 1,  
2! = 2,  
3! = 6,  
4! = 24,  
5! = 120.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 14  
Permutations  
A permutation is an ordered arrangement.  
The number of ordered ways to choose k objects from n distinct objects is  
n(n − 1) · · · (n − k + 1).  
Using factorial notation:  
n!  
(n − k)!  
This is denoted by  
P(n, k).  
So, in summary  
n!  
P(n, k) =  
= n(n − 1) · · · (n − k + 1).  
(n − k)!  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 15  
Example: Choosing Officers  
Suppose a club has 12 members.  
We choose:  
▶ a president,  
▶ a vice president,  
▶ a secretary.  
Since positions are different, order matters.  
Therefore:  
12!  
9!  
P(12, 3) =  
= 12 · 11 · 10 = 1320.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 16  
Combinations  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 17  
When Order Does Not Matter  
Suppose we choose a committee of size k from n people.  
Now:  
{A, B, C}  
{B, A, C}  
and  
represent the same committee.  
Thus order does not matter.  
This requires a different counting formula.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 18  
Binomial Coefficients  
Definition  
The number of subsets of size k from a set of size n is  
  !  
n
n!  
k!(n − k)!  
=
.
k
This is read as:  
“n choose k”.  
ꢀ ꢁ  
ꢀ ꢁ  
ꢀ ꢁ  
1
1
1
0
0
0
Note:  
=
=
= 1, can be justified by the formula or combinatorially.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 19  
Why Divide by k!?  
Suppose we first count ordered selections:  
n!  
P(n, k) =  
.
(n − k)!  
But each unordered subset is counted many times.  
For example {A, B, C} can appear as:  
ABC, ACB, BAC, BCA, CAB, CBA.  
There are 3! = 6 orderings.  
Therefore we divide by k!:  
  !  
  !  
n
n!  
P(n, k)  
n
k
=
=
⇒
≤ P(n, k).  
k
k!(n − k)!  
k!  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 20  
Example: Poker Hands  
A poker hand consists of 5 cards from a 52-card deck.  
Order does not matter.  
Thus the number of poker hands is  
 
!
52  
5
52!  
=
.
5!47!  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 21  
Example: Committees  
How many committees of size 4 can be formed from 10 people?  
Since order does not matter:  
 
!
10  
4
10!  
=
.
4!6!  
Simplifying:  
 
!
10  
= 210.  
4
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 22  
Properties of Binomial Coefficients  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 23  
Symmetry Identity  
Identity  
  !  
 
!
n
n
=
k
n − k  
Reason:  
Choosing k elements to include is equivalent to choosing n − k elements to exclude. :)  
Algebraic Proof:  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 24  
Khayyam–Pascal’s Identity  
Khayyam-Pascal’s Identity  
  !  
 
!
 
!
n
n − 1  
n − 1  
=
+
k
k
k − 1  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 25  
Combinatorial Proof of Khayyam-Pascal’s Identity  
Suppose a committee of size k is selected from n people.  
Focus on one distinguished person.  
Two possibilities:  
1
The distinguished person is not selected.  
Then choose all k members from the remaining n − 1 people:  
 
!
n − 1  
.
k
2
The distinguished person is selected.  
Then choose the remaining k − 1 members from the remaining n − 1 people:  
 
!
n − 1  
.
k − 1  
Adding the two cases gives (why addition?)  
  !  
 
!
 
!
n
k
n − 1  
n − 1  
=
+
.
k
k − 1  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 26  
Khayyam–Pascal Triangle: The Main Idea  
The Khayyam–Pascal triangle is a triangular arrangement of numbers.  
Each row begins and ends with 1.  
Every interior entry is obtained by adding the two entries directly above it:  
new entry = upper-left entry + upper-right entry  
1
1
1
1
4
2
6
1
4
1
3
3
1
1
1
Source: Wikipedia: Pascal’s Triangle.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 27  
Building the Triangle  
Start with 1 at the top.  
Each new number is the sum of the two numbers above it.  
1
1
1
1
1 + 1  
3 + 3  
1
1
1 + 2  
2 + 1  
1
1
1 + 3  
3 + 1  
1
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 28  
The Formula Inside the Triangle  
ꢀ ꢁ  
0
0
row 0  
row 1  
row 2  
row 3  
ꢀ ꢁ  
ꢀ ꢁ  
1
0
1
1
ꢀ ꢁ  
ꢀ ꢁ  
ꢀ ꢁ  
2
0
2
2
2
1
ꢀ ꢁ  
ꢀ ꢁ  
ꢀ ꢁ  
ꢀ ꢁ  
3
0
3
3
3
1
2
3
.
.
.
ꢀ
ꢁ
ꢀ
ꢁ
ꢀ
ꢁ
ꢀ
ꢁ
n−1  
n−1  
n−1  
n−1  
row n − 1  
· · ·  
· · ·  
0
k−1  
k
n−1  
ꢀ ꢁ  
ꢀ
ꢁ
ꢀ ꢁ  
ꢀ
ꢁ
ꢀ ꢁ  
n
0
n
k−1  
n
k
n
k+1  
n
n
row n  
· · ·  
· · ·  
Each interior entry is obtained by adding the two entries directly above it:  
ꢂ ꢃ  
ꢂ
ꢃ
ꢂ
ꢃ
n
n − 1  
n − 1  
=
+
k
k − 1  
k
This identity is known as Khayyam-Pascal’s Rule.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 29  
Khayyam-Pascal’s Rule/Identity  
The rule for building the triangle is  
  !  
 
!
 
!
n
n − 1  
n − 1  
=
+
k
k − 1  
k
for 1 ≤ k ≤ n − 1.  
For example,  
  !  
  !   !  
4
2
3
1
3
2
=
+
= 3 + 3 = 6.  
So every interior entry is obtained by adding the two entries above it.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 30  
Connection to Binomial Expansions  
The rows of the triangle give the coefficients in binomial expansions.  
(a + b)0 = 1  
(a + b)1 = a + b  
(a + b)2 = a2 + 2ab + b2  
(a + b)3 = a3 + 3a2b + 3ab2 + b3  
(a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4  
▶ The coefficients are exactly the rows of the Khayyam–Pascal triangle.  
ꢀ ꢁ  
P
n
k=0  
n
k
▶ Hence, we can show that (a + b)n =  
ak bn−k (a very useful identity in Probability theory.  
ꢀ ꢁ  
P
n
i=0  
n
▶ Also proves why 2n =  
.
k
Hint: 2 = 1 + 1 :)  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 31  
Story Proofs and Overcounting  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 32  
Story Proofs  
A story proof proves an identity by showing that both sides count the same object in different ways.  
Advantages:  
▶ gives intuition;  
▶ explains why identities are true;  
▶ often simpler than algebraic proofs.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 33  
Example Story Proof  
Identity  
  !  
n
X
n
= 2n.  
k
k=0  
Why?  
The left-hand side counts subsets of an n-element set by grouping according to subset size.  
The right-hand side counts subsets directly (see slide 60):  
each element is either:  
included or not included.  
Thus there are  
2n  
subsets total.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 34  
Overcounting  
A common counting mistake is to count the same object multiple times.  
Example:  
Suppose we want the number of unordered pairs from n people.  
If we count:  
n(n − 1),  
then each pair is counted twice:  
(A, B) and (B, A).  
Thus we divide by 2:  
  !  
n
n(n − 1)  
=
.
2
2
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 35  
Mini-Exercises  
1
How many binary strings of length 8 are there?  
2
How many 3-letter strings can be formed from the English alphabet if repetition is allowed?  
3
How many ordered arrangements of 4 people can be selected from 10 people?  
4
How many committees of size 3 can be formed from 8 people?  
Optional answers  
  !  
10!  
6!  
8
3
28 = 256,  
263,  
,
= 56.  
Arman Jahangiri  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 36  
Summary  
▶ With replacement:  
nk .  
▶ Without replacement:  
n!  
.
(n − k)!  
▶ Ordered selections:  
n!  
P(n, k) =  
.
.
(n − k)!  
▶ Unordered selections:  
  !  
n
n!  
=
k
k!(n − k)!  
▶ Binomial coefficients properties:  
  !  
 
!
n
n
=
,
k
n − k  
and  
  !  
 
!
 
!
n
n − 1  
n − 1  
=
+
.
k
k
k − 1  
ArmanNJaheanxgtiri lecture  
Chapter 1C–1D: Counting, Multiplication Rule, and Binomial Coefficie
Summer 2026 37