Topics

The Basics of Counting: The sum rule

The Basics of Counting: The product rule
The Subtraction Rule (Inclusion-Exclusion)
The Pigeonhole Principle
Permutations and Combinations
Binomial Coefficients and Identities

Mufleh Al-Shatnawi, Ph.D., [Link]., 1

The Basics of
Counting

Mufleh Al-Shatnawi, Ph.D., [Link]., 2

Introduction
Count the number of ways to put things together into various
combinations.
Counting problems are of the following kind:
“How many different 8-letter passwords are there?”
“How many possible ways are there to pick 11 soccer players out of a
20-player team?”

Most importantly, counting is the basis for computing

probabilities of discrete events.
(“What is the probability of winning the lottery?”)

Mufleh Al-Shatnawi, Ph.D., [Link]., 3

Introduction
Although counting seems to be a simple straightforward
task, many counting questions end up being quite
counterintuitive.
A couple of intuitive rules, the sum and product rules, will
first be introduced. Using these, we will derive some
interesting results and show how to tackle more difficult
counting problems.
One should not be discouraged if their initial approach is
foiled or seems too difficult. Oftentimes, different approaches
to the same problem will eventually yield a simple solution.
Mufleh Al-Shatnawi, Ph.D., [Link]., 4
Basic Counting
Principles
THE SUM RULE

Mufleh Al-Shatnawi, Ph.D., [Link]., 5

Basic Counting Principles
The sum rule:
If a task can be done either in one of 𝒏𝒏𝟏𝟏 ways or in
one of 𝒏𝒏𝟐𝟐 ways, where none of the set of 𝒏𝒏𝟏𝟏 ways is
the same as any of the set of 𝒏𝒏𝟐𝟐 ways, then there are
𝒏𝒏𝟏𝟏 + 𝒏𝒏𝟐𝟐 ways to do the task.

If a task can be done in 𝒏𝒏𝟏𝟏 ways and a second task in

𝒏𝒏𝟐𝟐 ways, and if these two tasks cannot be done at
the same time, then there are 𝒏𝒏𝟏𝟏 + 𝒏𝒏𝟐𝟐 ways to do
either task.
Mufleh Al-Shatnawi, Ph.D., [Link]., 6
Basic Counting Principles
The sum rule:
Since most counting questions do not involve any action, We can
use the following version of the definition:
If you have 𝒎𝒎 objects in one group, and 𝒏𝒏 objects in
a second group, which is completely separate from the
first, (meaning that they share no common objects),
then the total number of objects in both groups is 𝒎𝒎 + 𝒏𝒏.

Here is a set definition: The cardinality of the union of

two disjoint sets is the sum of each set's cardinality.
Mufleh Al-Shatnawi, Ph.D., [Link]., 7
Example:
The department will award a free computer to either a
CS student or a CS professor.
How many different choices are there, if there are 530
students and 15 professors?
There are 530 + 15 = 545 choices.

Sum rule: the number of ways that “either task1 or task2

can be done, but not both”, is m+n.

Mufleh Al-Shatnawi, Ph.D., [Link]., 8

Basic Counting Principles
Generalized sum rule:
If we have tasks 𝑇𝑇1 , 𝑇𝑇2 , … 𝑇𝑇𝑛𝑛 that can be done in
𝑛𝑛1, 𝑛𝑛2, … , 𝑛𝑛𝑚𝑚 ways, respectively, and no two of
these tasks can be done at the same time,
then there are 𝒏𝒏𝟏𝟏 + 𝒏𝒏𝟐𝟐 + … + 𝒏𝒏𝒎𝒎 ways to do
one of these tasks.

Mufleh Al-Shatnawi, Ph.D., [Link]., 9

Example
A student can choose a computer project from one of three lists.
The three lists contain 23, 15, and 19 possible projects,
respectively. How many possible projects are there to choose
from? No project is on more than one list.

The student can choose a project by selecting a project from the

first list, the second list, or the third list. Because no project is on
more than one list, by the sum rule there are 23 + 15 + 19 = 57
ways to choose a project.

Mufleh Al-Shatnawi, Ph.D., [Link]., 10

Example
What is the value of 𝑘𝑘 after the following code, where
𝑛𝑛1 , 𝑛𝑛2 , … , 𝑛𝑛𝑚𝑚 are positive integers, has been executed?

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

Mufleh Al-Shatnawi, Ph.D., [Link]., 11

Basic Counting
Principles
THE PRODUCT RULE

Mufleh Al-Shatnawi, Ph.D., [Link]., 12

Basic Counting Principles
The product rule
Suppose that a procedure can be broken down into two
successive tasks. If there are 𝒏𝒏𝟏𝟏 ways to do the first task and
𝒏𝒏𝟐𝟐 ways to do the second task after the first task has been
done, then there are (𝒏𝒏𝟏𝟏 𝒏𝒏𝟐𝟐 ) ways to do the procedure.
Here's a definition using sets: The cardinality of the
cartesian product of two sets is the product of each set's
cardinality
𝐴𝐴1 × 𝐴𝐴2 × ⋯ × 𝐴𝐴𝑚𝑚 = 𝐴𝐴1 ⋅ 𝐴𝐴2 ⋅ ⋯ ⋅ 𝐴𝐴𝑚𝑚

Mufleh Al-Shatnawi, Ph.D., [Link]., 13

Example
How many different license plates are there that
contain exactly three English letters?

Solution:
There are 26 possibilities to pick the first letter, then
26 possibilities for the second one, and 26 for the last
one.
So there are 26⋅26⋅26 = 17576 different license plates.

Mufleh Al-Shatnawi, Ph.D., [Link]., 14

Example
The chairs of an auditorium are to be labeled with an
uppercase English letter followed by a positive integer not
exceeding 100. What is the largest number of chairs that can
be labeled differently?
Solution
The procedure of labeling a chair consists of two tasks, namely,
assigning to the seat one of the 26 uppercase English letters, and
then assigning to it one of the 100 possible integers.
The product rule shows that there are 26 ⋅ 100 = 2600 different
ways that a chair can be labeled.
Therefore, the largest number of chairs that can be labeled
differently is 2600.
Mufleh Al-Shatnawi, Ph.D., [Link]., 15
Basic Counting Principles
Generalized product rule:
If we have a procedure consisting of sequential
tasks 𝑇𝑇1 , 𝑇𝑇2 , … , 𝑇𝑇𝑚𝑚 that can be done in
𝑛𝑛1 , 𝑛𝑛2 , … , 𝑛𝑛𝑚𝑚 ways, respectively, then there are
(𝒏𝒏𝟏𝟏 ) ⋅ (𝒏𝒏𝟐𝟐 ) ⋅ ⋯ ⋅ (𝒏𝒏𝒎𝒎 ) ways to carry out the
procedure.

Mufleh Al-Shatnawi, Ph.D., [Link]., 16

Example
What is the value of 𝑘𝑘 after the following code, where
𝑛𝑛1 , 𝑛𝑛2 , … , 𝑛𝑛𝑚𝑚 are positive integers, has been executed?

𝑘𝑘 = 𝑛𝑛1 𝑛𝑛2 ⋯ (𝑛𝑛𝑚𝑚 )

Mufleh Al-Shatnawi, Ph.D., [Link]., 17

Example
 Count the number of print statements in this algorithm:

for i := 1 to n
begin
for j := 1 to n
print “hello”
for k := 1 to n
print “hello”
end

 The total number of print statements executed is

𝒏𝒏 · (𝒏𝒏 + 𝒏𝒏) = 𝟐𝟐𝟐𝟐𝟐𝟐

Mufleh Al-Shatnawi, Ph.D., [Link]., 18

Example
 Count the number of print statements in this algorithm:
for i := 1 to n
begin
for j := 1 to i
print “hello”
for k := i+1 to n
print “hello”
end

for each 𝑖𝑖 from outer loop, the number of print statements executed is 𝒊𝒊 in
the 𝒋𝒋 loop (first inner loop) plus 𝒏𝒏 − 𝒊𝒊 in the 𝒌𝒌 loop. Therefore, for each 𝒊𝒊, the
number of print statements is: 𝒊𝒊 + (𝒏𝒏 − 𝒊𝒊) = 𝒏𝒏
Therefore, the total number of print statements executed is 𝒏𝒏 · 𝒏𝒏 = 𝒏𝒏𝟐𝟐.
Mufleh Al-Shatnawi, Ph.D., [Link]., 19
Example
Each user on a computer system has a password, which is six
to eight characters long, where each character is an
uppercase letter or a digit. Each password must contain at
least one digit. How many possible passwords are there?

Mufleh Al-Shatnawi, Ph.D., [Link]., 20

Example Cont.
Each user on a computer system has a password, which is six to eight
characters long, where each character is an uppercase letter or a digit.
Each password must contain at least one digit. How many possible
passwords are there?
Solution
(string includes Letters & Digits) - (string with no digits)

𝑃𝑃 = 𝑃𝑃6 + 𝑃𝑃7 + 𝑃𝑃8

𝑃𝑃6 = 366 − 266 = 1867866560
𝑃𝑃7 = 367 − 267 = 70332353920
𝑃𝑃8 = 368 − 268 = 2612282842880

𝑷𝑷 = 𝑷𝑷𝟔𝟔 + 𝑷𝑷𝟕𝟕 + 𝑷𝑷𝟖𝟖 = 𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐𝟐

Mufleh Al-Shatnawi, Ph.D., [Link]., 21

The Subtraction Rule
(Inclusion–Exclusion)

Mufleh Al-Shatnawi, Ph.D., [Link]., 22

The Subtraction Rule (Inclusion–Exclusion)
If a task can be done in either 𝒏𝒏𝟏𝟏 ways or 𝑛𝑛2 ways, then the
number of ways to do the task is 𝒏𝒏𝟏𝟏 + 𝒏𝒏𝟐𝟐 minus the number of
ways to do the task that are common to the two different ways.

The number of elements in the set ¬𝑨𝑨 from an universe 𝑈𝑈 is

simply |𝑈𝑈| − |𝐴𝐴|.

Mufleh Al-Shatnawi, Ph.D., [Link]., 23

Example
How many bit strings of length 8 either start with a 1 or
end with 00?
Task 1: Construct a string of length 8 that starts with a 1.
There is one way to pick the first bit (1),
two ways to pick the second bit (0 or 1),
two ways to pick the third bit (0 or 1),
.
.
.
two ways to pick the eighth bit (0 or 1).
Product rule: Task 1 can be done in 1⋅27 = 128 ways.
Mufleh Al-Shatnawi, Ph.D., [Link]., 24
Example Cont.
Task 2: Construct a string of length 8 that ends with 00.
There are two ways to pick the first bit (0 or 1),
two ways to pick the second bit (0 or 1),
.
.
.
two ways to pick the sixth bit (0 or 1),
one way to pick the seventh bit (0), and
one way to pick the eighth bit (0).

Product rule: Task 2 can be done in 26 = 64 ways.

Mufleh Al-Shatnawi, Ph.D., [Link]., 25

Example Cont.
Since there are 128 ways to do Task 1 and 64 ways to
do Task 2, does this mean that there are 192 bit strings
either starting with 1 or ending with 00?
No, because here Task 1 and Task 2 can be done at the
same time.
When we carry out Task 1 and create strings starting with 1,
some of these strings end with 00.
Therefore, we sometimes do Tasks 1 and 2 at the same
time, so the sum rule does not apply.

Mufleh Al-Shatnawi, Ph.D., [Link]., 26

Example Cont.
If we want to use the sum rule in such a case, we must subtract
the cases when Tasks 1 and 2 are done at the same time.
How many cases are there, that is, how many strings start with
1 and end with 00?
There is one way to pick the first bit (1),
two ways for the second, …, sixth bit (0 or 1),
one way for the seventh, eighth bit (0).

Product rule: In 25 = 32 cases, Tasks 1 and 2 are carried out at

the same time.

Mufleh Al-Shatnawi, Ph.D., [Link]., 27

Example Cont.
Since there are 128 ways to complete Task 1 and 64
ways to complete Task 2, and in 32 of these cases Tasks
1 and 2 are completed at the same time, there are
128 + 64 – 32 = 160 ways to do either task.
In set theory, this corresponds to sets A1 and A2 that are
not disjoint. Then we have:
|A1 ∪ A2| = |A1| + |A2| - |A1 ∩ A2|
This is called the principle of inclusion-exclusion.

Mufleh Al-Shatnawi, Ph.D., [Link]., 28

Example
How many seven-digit phone numbers (where leading 0s are
acceptable) do not contain the substring 1234?
Solution:
Using the product rule, there are 107 valid phone numbers.
Of these, we need to count how many contain the substring 1234. Here are our
possibilities:
1 2 3 4 __ __ __ __ 1 2 3 4 __ __ __
__ __ 1 2 3 4 __ __ __ __ 1 2 3 4
Each of account for 103 numbers with the substring 1234.
Thus, our final answer is 107 − 4(103 ) = 9996000.

Mufleh Al-Shatnawi, Ph.D., [Link]., 29

Tree Diagrams
How many bit strings of length four do not have two
consecutive 1s?
Task 1 Task 2 Task 3 Task 4
(1st bit) (2nd bit) (3rd bit) (4th bit)
0
0
0
1
0 1
0
1 0 0
1
0 0
1 0
1
1
0
There are 8 strings.

Mufleh Al-Shatnawi, Ph.D., [Link]., 30

The Pigeonhole Principle

Mufleh Al-Shatnawi, Ph.D., [Link]., 31

The Pigeonhole Principle
The pigeonhole principle: If (k + 1) or more objects
are placed into k boxes, then there is at least one box
containing two or more of the objects.

Example 1: If there are 11 players in a soccer team

that wins 12-0, there must be at least one player in the
team who scored at least twice.
Example 2: If you have 6 classes from Monday to
Friday, there must be at least one day on which you
have at least two classes.
Mufleh Al-Shatnawi, Ph.D., [Link]., 32
The Pigeonhole Principle
In terms of the assignment function:
If 𝑓𝑓: 𝐴𝐴 → 𝐵𝐵 and |𝐴𝐴| ≥ |𝐵𝐵| + 1, then some element of B has ≥ 2
pre-images under 𝑓𝑓.( 𝑓𝑓 is not one-to-one)

How many students must be in class to guarantee that at least

two students receive the same score on the final exam, if the
exam is graded on a scale from 0 to 100 points? Greater than
101

Mufleh Al-Shatnawi, Ph.D., [Link]., 33

The Pigeonhole Principle
The generalized pigeonhole principle: If N objects
are placed into k boxes, then there is at least one box
containing at least N/k of the objects.
Example 1: In our 60-student class, at least 12
students will get the same letter grade (A, B, C, D, or F).

Example 2: there are N=280 students in this class.

There are k=52 weeks in the year.
Therefore, there must be at least 1 week during which at least
280/52= 5.38=6 students in the class have a birthday.

Mufleh Al-Shatnawi, Ph.D., [Link]., 34

Example
Assume you have a drawer containing a random
distribution of a dozen brown socks and a dozen
black socks. It is dark, so how many socks do you
have to pick to be sure that among them there is a
matching pair?
Solution:
There are two types of socks, so if you pick at least 3 socks,
there must be either at least two brown socks or at least two
black socks.
Generalized pigeonhole principle: 3/2 = 2.

Mufleh Al-Shatnawi, Ph.D., [Link]., 35

Permutations and
Combinations

Mufleh Al-Shatnawi, Ph.D., [Link]., 36

Permutations and Combinations
Counting:
Find out the number of ways to select a particular number
of elements from a set
Sometimes the order of these elements matter
Example:
How many ways we can select 3 students from a group of
5 students?
How many different ways do they stand in line for a
picture?

Mufleh Al-Shatnawi, Ph.D., [Link]., 37

Permutations

Mufleh Al-Shatnawi, Ph.D., [Link]., 38

Permutation
A permutation of objects is simply an arrangement of
those objects.
A common example of permutations deals with words.
How many “words” can you form out of the letters A,
B, C, and D, without repeating a letter.

Essentially, the question boils down to how many ways

can you order a set of objects.

Mufleh Al-Shatnawi, Ph.D., [Link]., 39

Permutation
How many ways can we select three students from a
group of 5 to stand in lines for a picture?
First, note that the order in which we select students
matters
There are five ways to select the 1st student
Once the 1st student is selected, there are four ways to
select the 2nd student in line.
By product rule, there are 5x4x3=60 ways to select
three students from a group of 5 students to stand in line
for a picture
Mufleh Al-Shatnawi, Ph.D., [Link]., 40
Permutation
How many ways can we arrange all 5 in a line for a
picture?
By product rule, we have 5x4x3x2x1=120 ways to
arrange all 5 students in a line for a picture

Mufleh Al-Shatnawi, Ph.D., [Link]., 41

Permutation
A permutation of a set of distinct objects is an ordered
arrangement of these objects
An ordered arrangement of r elements of a set is called an r-
permutation
The number of r-permutation of a set with n elements
is denoted by 𝑃𝑃(𝑛𝑛, 𝑟𝑟).
We can find 𝑃𝑃(𝑛𝑛, 𝑟𝑟) using the product rule
Example: Let 𝑆𝑆 = {1, 2, 3}.
The ordered arrangement 3, 1, 2 is a permutation of S.
The ordered arrangement 3, 2, is a 2-permutation of S

Mufleh Al-Shatnawi, Ph.D., [Link]., 42

Permutation
Let 𝑆𝑆 = {𝑎𝑎, 𝑏𝑏, 𝑐𝑐}.
The 2-permutation of S are the ordered
arrangements, a, b; a, c; b, a; b, c; c, a; and c, b
Consequently, there are 6 2-permutation of this set
with 3 elements
Note that there are 3 ways to choose the 1st element
and then 2 ways to choose the 2nd element
By product rule, there are 𝑃𝑃 3,2 = 3 × 2 = 6

Mufleh Al-Shatnawi, Ph.D., [Link]., 43

r-permutation
Theorem 1: If 𝑛𝑛 is a positive and 𝑟𝑟 is an integer with 1 ≤ 𝑟𝑟 ≤ 𝑛𝑛,
then there are
𝑷𝑷(𝒏𝒏, 𝒓𝒓) = 𝒏𝒏(𝒏𝒏 − 𝟏𝟏)(𝒏𝒏 − 𝟐𝟐) … (𝒏𝒏 − 𝒓𝒓 + 𝟏𝟏)
r-permutations of a set with 𝑛𝑛 elements
Proof:
Use the product rule, the first element can be chosen in n ways.
There are n-1 ways to chose the 2nd element.
Likewise, there are n-2 ways to choose 3rd element, and so on until there
are exactly 𝒏𝒏 − (𝒓𝒓 − 𝟏𝟏) = 𝒏𝒏 − 𝒓𝒓 + 𝟏𝟏 ways to choose the r-th element.
Thus, there are 𝒏𝒏 � 𝒏𝒏 − 𝟏𝟏 � 𝒏𝒏 − 𝟐𝟐 ⋅ ⋯ � (𝒏𝒏 − 𝒓𝒓 + 𝟏𝟏) r-permutations of
the set
Mufleh Al-Shatnawi, Ph.D., [Link]., 44
r-permutation
Note that 𝑷𝑷(𝒏𝒏, 𝟎𝟎) = 𝟏𝟏 whenever 𝑛𝑛 is a non-negative
integer as there is exactly one way to order zero element
Corollary 1: If 𝑛𝑛 and 𝑟𝑟 are integers with 0 ≤ 𝑟𝑟 ≤ 𝑛𝑛, then
𝒏𝒏!
𝑃𝑃(𝑛𝑛, 𝑟𝑟) =
𝒏𝒏 − 𝒓𝒓 !
Note: For those of you unfamiliar with the ! notation, it is read
as “factorial”.
𝒏𝒏! is simply defined as the product of all the positive
integers in between 1 and n, inclusive.)

Mufleh Al-Shatnawi, Ph.D., [Link]., 45

r-permutation
Corollary 1: If 𝑛𝑛 and 𝑟𝑟 are integers with 0 ≤ 𝑟𝑟 ≤ 𝑛𝑛, then
𝒏𝒏!
𝑃𝑃(𝑛𝑛, 𝑟𝑟) =
𝒏𝒏 − 𝒓𝒓 !
Proof: When 𝑛𝑛 and 𝑟𝑟 are integers with 1 ≤ 𝑟𝑟 ≤ 𝑛𝑛, by Theorem 1
we have
𝒏𝒏!
𝑃𝑃(𝑛𝑛, 𝑟𝑟) = 𝒏𝒏(𝒏𝒏 − 𝟏𝟏) … (𝒏𝒏 − 𝒓𝒓 + 𝟏𝟏) =
𝒏𝒏 − 𝒓𝒓 !
As 𝑛𝑛!/(𝑛𝑛 − 0)! = 1 when 𝑛𝑛 is a nonnegative integer, we have
𝑃𝑃(𝑛𝑛, 𝑟𝑟) = 𝑛𝑛!/(𝑛𝑛 − 𝑟𝑟)! also holds when 𝒓𝒓 = 𝟎𝟎

Mufleh Al-Shatnawi, Ph.D., [Link]., 46

r-permutation
By Theorem 1, we know that if 𝑛𝑛 is a positive integer, then
𝑃𝑃(𝑛𝑛, 𝑛𝑛) = 𝑛𝑛!
Example: How many ways are there to select a 1st prize
winner, a 2nd prize winner, and a 3rd prize winner from 100
different contestants?
𝑃𝑃 100,3 = 100 × 99 × 98 = 970,200

Mufleh Al-Shatnawi, Ph.D., [Link]., 47

Example
How many permutations of the letters ABCDEFGH
contain string ABC?
As ABC must occur as a block, we can find the
answer by finding the permutations of 6 letters, the block
ABC and the individual letters, D, E, F, G, and H.
As these 6 objects must occur in any order, there are
6!=720 permutations of the letters ABCDEFGH in which
ABC occurs in a block

Mufleh Al-Shatnawi, Ph.D., [Link]., 48

Combinations

Mufleh Al-Shatnawi, Ph.D., [Link]., 49

Combinations
How many different committees of 3 students can be
formed from a group of 4 students?
We need to find the number of subsets with 3 elements from
the set containing 4 students

A subset simply is any group (with a size in between 0

and n, inclusive) of the n objects. The order in which the
members of the subset are picked does not matter

Mufleh Al-Shatnawi, Ph.D., [Link]., 50

Combinations
How many different committees of 3 students can be
formed from a group of 4 students?
We need to find the number of subsets with 3 elements from the
set containing 4 students
We see that there are 4 such subsets
for each one we are choosing one of the 4 students to leave out of
the group
This means there are 4 ways to choose 3 students for the
committee, where the order in which these students are
chosen does not matter
Mufleh Al-Shatnawi, Ph.D., [Link]., 51
r-combinations
An r-combination of elements of a set is an
unordered selection of 𝑟𝑟 elements from the set
An r-combination is simply a subset of the set with
𝑟𝑟 elements. Denote by 𝐶𝐶(𝑛𝑛, 𝑟𝑟).
𝒏𝒏
Note that 𝐶𝐶(𝑛𝑛, 𝑟𝑟) is also denoted by 𝒓𝒓
and is
called a binomial coefficient
𝐶𝐶 𝑛𝑛, 𝑟𝑟 : This can be read as “n choose r”.

Mufleh Al-Shatnawi, Ph.D., [Link]., 52

Example
Let 𝑆𝑆 be the set {1, 2, 3, 4}. Then {1, 3, 4} is a 3-
combination from 𝑆𝑆
We see that 𝐶𝐶(4,2) = 6, as the 2-combination of
{𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑} are 6 subsets {a, b}, {a, c}, {a, d}, {b, c},
{b, d}, and {c, d}

Mufleh Al-Shatnawi, Ph.D., [Link]., 53

Example
Consider the 3-combination (a subset of size 3) of the
letters K, N, I, G, H, T, and S.

One of these combinations is G, I, and N.

Now, consider listing all of the permutations of size 3
that “correspond” to this one combination:
GIN, GNI, IGN, ING, NGI, and NIG.
In particular, there are 3! of these combinations.

Mufleh Al-Shatnawi, Ph.D., [Link]., 54

Example Cont.
Consider the 3-combination (a subset of size 3) of the letters K,
N, I, G, H, T, and S.
Thus, when we count the number of permutations of size 3,
we are counting each combination 3! times.
In general, when we count the number of permutations of size
k, we are counting each combination k! times.
So, the answer to our original question is
𝑛𝑛!
𝑛𝑛 − 𝑘𝑘 ! 𝑘𝑘!
Mufleh Al-Shatnawi, Ph.D., [Link]., 55
r-combinations
We can determine the number of r-combinations of a
set with 𝑛𝑛 elements using the formula for the number of r-
permutations of a set

Note that the r-permutations of a set can be obtained

by first forming r-combinations and then ordering the
elements in these combinations

Mufleh Al-Shatnawi, Ph.D., [Link]., 56

r-combinations
The number of r-combinations of a set with 𝑛𝑛 elements, where 𝑛𝑛 is a
nonnegative integer and 𝑟𝑟 is an integer with 0 ≤ 𝑟𝑟 ≤ 𝑛𝑛 equals
𝑛𝑛!
𝐶𝐶 𝑛𝑛, 𝑟𝑟 =
𝑟𝑟! 𝑛𝑛 − 𝑟𝑟 !
Proof: The r-permutations of the set can be obtained by forming the C(n,r) r-
combinations and then ordering the elements in each r-permutation which can
be done in 𝑃𝑃(𝑟𝑟, 𝑟𝑟) ways

𝑃𝑃 𝑛𝑛, 𝑟𝑟 = 𝐶𝐶 𝑛𝑛, 𝑟𝑟 𝑃𝑃 𝑟𝑟, 𝑟𝑟

𝑃𝑃(𝑛𝑛, 𝑟𝑟) 𝑛𝑛!⁄ 𝑛𝑛 − 𝑟𝑟 ! 𝑛𝑛!

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

Mufleh Al-Shatnawi, Ph.D., [Link]., 57

r-combination
When computing r-combination
𝑛𝑛! 𝑃𝑃(𝑛𝑛, 𝑟𝑟)
𝐶𝐶 𝑛𝑛, 𝑟𝑟 = =
𝑟𝑟! 𝑛𝑛 − 𝑟𝑟 ! 𝑟𝑟!

𝑛𝑛 𝑛𝑛 − 1 𝑛𝑛 − 2 ⋯ (𝑛𝑛 − 𝑟𝑟 + 1)
𝐶𝐶(𝑛𝑛. 𝑟𝑟) =
𝑟𝑟!
thus, canceling out all the terms in the larger factorial

Mufleh Al-Shatnawi, Ph.D., [Link]., 58

Example
How many poker hands of 5 cards can be dealt from a
standard deck of 52 cards? Also, how many ways are there
to select 47 cards from a standard deck of 52 cards?
Solution:
Choose 5 out of 52 cards:
52! 52 × 51 × 50 × 49 × 48
𝐶𝐶 52,5 = =
5! 47! 5×4× 3×2×1
= 26 × 17 × 10 × 49 × 12 = 2,598,960

52!
𝐶𝐶(52,47) = = 2,5,98,960
47! 5!
Mufleh Al-Shatnawi, Ph.D., [Link]., 59
Corollary 2
Let 𝑛𝑛 and 𝑟𝑟 be nonnegative integers with 𝑟𝑟 ≤ 𝑛𝑛. Then
𝐶𝐶(𝑛𝑛, 𝑟𝑟) = 𝐶𝐶(𝑛𝑛, 𝑛𝑛 − 𝑟𝑟)
Proof:
𝑛𝑛!
𝐶𝐶 𝑛𝑛, 𝑟𝑟 =
𝑟𝑟! 𝑛𝑛 − 𝑟𝑟 !
𝑛𝑛! 𝑛𝑛!
𝐶𝐶 𝑛𝑛, 𝑛𝑛 − 𝑟𝑟 = =
𝑛𝑛 − 𝑟𝑟 ! 𝑛𝑛 − 𝑛𝑛 − 𝑟𝑟 ! 𝑟𝑟! 𝑛𝑛 − 𝑟𝑟 !

Mufleh Al-Shatnawi, Ph.D., [Link]., 60

Example
How many ways are there to select 5 players from a
10-member tennis team?
Choose 5 out of 10 elements, i.e.,
10!
𝐶𝐶(10, 5) = = 252
5! 5!
How many bit strings of length 𝒏𝒏 contain exactly 𝑟𝑟 1s?
This is equivalent to choose 𝑟𝑟 elements from 𝑛𝑛
elements, i.e., 𝐶𝐶(𝑛𝑛, 𝑟𝑟)

Mufleh Al-Shatnawi, Ph.D., [Link]., 61

Example
Consider choosing a senate committee of five members. There
are 35 women in the senate and 65 men. How many
committees can you pick with exactly three men?
Solution:
We know that if we have three men, we must have exactly two women
on the committee.
The choices of the men and women are independent.
We can choose the women in 𝐶𝐶(35, 2) ways, and we can choose the men
in 𝐶𝐶(65, 3) ways.
The total number of committee choices will simply be the product of
these two values.

Mufleh Al-Shatnawi, Ph.D., [Link]., 62

Binomial Coefficients
and Identities

Mufleh Al-Shatnawi, Ph.D., [Link]., 63

Binomial Coefficients
The number of r-combinations form a set with 𝑛𝑛
elements is often denoted by
𝑛𝑛
𝑟𝑟
Also called as a binomial coefficient as these
numbers occur as coefficients in the expansion of powers
of binomial expressions such as 𝑎𝑎 + 𝑏𝑏 𝑛𝑛
A binomial expression is simply the sum of two terms, such as
𝑥𝑥 + 𝑦𝑦

Mufleh Al-Shatnawi, Ph.D., [Link]., 64

Example
The expansion of (𝑥𝑥 + 𝑦𝑦)3 can be found using
combinational reasoning instead of multiplying the three
terms out
When (𝑥𝑥 + 𝑦𝑦)3 = (𝑥𝑥 + 𝑦𝑦)(𝑥𝑥 + 𝑦𝑦)(𝑥𝑥 + 𝑦𝑦) is expanded, all
products of a term in the 1st sum, a term in the 2nd sum,
and a term in the 3rd sum are added, e.g., x3, x2y, xy2,
and y3
To obtain a term of the form x3, an x must be chosen in
each of the sums, and this can be done in only one way.
Thus, the x3 term in the product has a coefficient of 1
Mufleh Al-Shatnawi, Ph.D., [Link]., 65
Example Cont.
To obtain a term of the form x2y, an x must be chosen in
2 of the 3 sums (and consequently a y in the other sum).
Hence, the number of such terms is the number of 2-
3
combinations of 3 objects, namely, 2

Similarly, the number of terms of the form xy2 is the

number of ways to pick 1 of the 3 sums to obtain an x
(and consequently take a y from each of the other two
3
sums), which can be done in 1 ways
Mufleh Al-Shatnawi, Ph.D., [Link]., 66
Example
Consequently,
( x + y ) 3 = ( x + y )( x + y )( x + y ) = ( xx + xy + yx + yy )( x + y )
= xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy
= x 3 + 3 x 2 y + 3 xy 2 + y 3

The binomial theorem: Let 𝑥𝑥 and 𝑦𝑦 be variables, and let 𝑛𝑛 be a

nonnegative integer
n
 n  n− j j
( x + y ) = ∑   x y
n

j =0  j 

 n  n  n  n −1  n  n − 2 2  n  n −1  n  n
=   x +   x y +   x y +  +   xy +   y
0 1  2  n − 1 n
Mufleh Al-Shatnawi, Ph.D., [Link]., 67
Binomial Theorem
n
 n  n− j j
( x + y ) = ∑   x y
n

j =0  j 

 n  n  n  n −1  n  n − 2 2  n  n −1  n  n
=   x +   x y +   x y +  +   xy +   y
0 1  2  n − 1 n

Proof: A combinatorial proof of the theorem is given. The terms in

the product when it is expanded are of the form xn-jyj for j=0,1,2…, n
To count the number of terms of the form xn-jyj , note that to obtain
such a term it is necessary to choose n-j x’s from the n sums (so
that the other j terms in the product are y’s). Therefore, the
𝑛𝑛
coefficients of xn-jyj is 𝑛𝑛−𝑗𝑗 which is equal to 𝑛𝑛𝑗𝑗

Mufleh Al-Shatnawi, Ph.D., [Link]., 68

Example
4
 4  4− j j
( x + y ) = ∑   x y
4

j =0  j 

 4 4  4 3  4 2 2  4 3  4 4
=   x +   x y +   x y +   xy +   y
0 1  2  3  4

What is the coefficient of x12y13 in the expansion of (x+y)25?

 25  25!
  = = 5,200,300
 13  13!12!

Mufleh Al-Shatnawi, Ph.D., [Link]., 69

Example
What is the coefficient of x12y13 in the expansion of (2x-3y)25?

25
 25 
(2 x − 3 y ) = ∑  (2 x) (−3 y )
25 25 − j j

j =0  j 

Consequently, the coefficient of x12y13 is

 25  12 25! 12 13
 2 (−3) = −
13
2 3
 13  13!12!
Mufleh Al-Shatnawi, Ph.D., [Link]., 70
Corollary
Corollary 1: Let 𝑛𝑛 be a nonnegative integer. Then
𝑛𝑛
𝑛𝑛
� = 2𝑛𝑛
𝑘𝑘
𝑘𝑘=0

Proof: Using Binomial theorem with 𝑥𝑥 = 1 and 𝑦𝑦 = 1

𝑛𝑛 𝑛𝑛
𝑛𝑛 𝑘𝑘 𝑛𝑛−𝑘𝑘 𝑛𝑛
2𝑛𝑛 = 1+1 𝑛𝑛 =� 1 1 =�
𝑘𝑘 𝑘𝑘
𝑘𝑘=0 𝑘𝑘=0

Mufleh Al-Shatnawi, Ph.D., [Link]., 71

Corollary 2
Let 𝑛𝑛 be a positive integer. Then
𝑛𝑛
𝑘𝑘
𝑛𝑛
� −1 =0
𝑘𝑘
𝑘𝑘=0

Proof:
𝑛𝑛 𝑛𝑛
𝑛𝑛 𝑛𝑛
0= 0𝑛𝑛 = ( −1 + 1 𝑛𝑛 =� −1 𝑘𝑘 1𝑛𝑛−𝑘𝑘 =� −1 𝑘𝑘
𝑘𝑘 𝑘𝑘
𝑘𝑘=0 𝑘𝑘=0
Corollary 2 implies that:
𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛
+ + +⋯= + + +⋯
0 2 4 1 3 5
Mufleh Al-Shatnawi, Ph.D., [Link]., 72
Corollary 3
Let 𝑛𝑛 be a nonnegative integer. Then
𝑛𝑛
𝑘𝑘
𝑛𝑛
� 2 = 3𝑛𝑛
𝑘𝑘
𝑘𝑘=0

Proof:
𝑛𝑛 𝑛𝑛
𝑛𝑛
𝑛𝑛 𝑘𝑘 1𝑛𝑛−𝑘𝑘
𝑛𝑛 𝑘𝑘
2+1 =� 2 =� 2
𝑘𝑘 𝑘𝑘
𝑘𝑘=0 𝑘𝑘=0

Mufleh Al-Shatnawi, Ph.D., [Link]., 73

Pascal Identity and Triangle
Pascal’s identity: Let 𝑛𝑛 and 𝑘𝑘 be positive integers with 𝑛𝑛 ≥ 𝑘𝑘.
Then
𝑛𝑛 + 1 𝑛𝑛 𝑛𝑛
= +
𝑘𝑘 𝑘𝑘 − 1 𝑘𝑘
Combinatorial proof: Let 𝑇𝑇 be a set containing 𝑛𝑛 + 1 elements.
Let 𝒂𝒂 be an element in 𝑇𝑇, and let 𝑺𝑺 = 𝑇𝑇 − {𝒂𝒂} (S has n elements)

Note that there are 𝑛𝑛+1

𝑘𝑘
subsets of 𝑇𝑇 containing 𝑘𝑘 elements.
However, a subset of 𝑇𝑇 with 𝑘𝑘 elements either contains 𝒂𝒂 (i.e., a
subset of k-1 elements of S) or not.
Mufleh Al-Shatnawi, Ph.D., [Link]., 74
Pascal Identity and Triangle Cont.
Pascal’s identity: Let 𝑛𝑛 and 𝑘𝑘 be positive integers with 𝑛𝑛 ≥ 𝑘𝑘.
Then
𝑛𝑛 + 1 𝑛𝑛 𝑛𝑛
= +
𝑘𝑘 𝑘𝑘 − 1 𝑘𝑘
𝑛𝑛
There are 𝑘𝑘−1
subsets of k-1 elements of S, and so there are
𝑛𝑛
𝑘𝑘−1
subsets of k-1 elements containing 𝒂𝒂
𝑛𝑛
There are 𝑘𝑘
subsets of k elements of T that do not contain 𝒂𝒂
𝑛𝑛+1 𝑛𝑛 𝑛𝑛
Thus 𝑘𝑘
= 𝑘𝑘−1
+ 𝑘𝑘

Mufleh Al-Shatnawi, Ph.D., [Link]., 75

Pascal Identity and Triangle
Can also prove the Pascal identity with algebraic manipulation
of 𝑛𝑛𝑘𝑘

 n + 1 (n + 1)!
  =
 k  k!(n − k + 1)!
 n  n! kn! kn!
  = = =
 k − 1 (k − 1)!(n − k + 1)! (k − 1)!k (n − k + 1)! k!(n − k + 1)!
n n! (n − k + 1)n! (n − k + 1)n!
  = = =
 k  k!(n − k )! k!(n − k )!(n − k + 1) k!(n − k + 1)!
 n  n kn! (n − k + 1)n! (k + n − k + 1)n! (n + 1)n! (n + 1)!
  +   = + = = =
 k − 1  k  k!(n − k + 1)! k!(n − k + 1)! k!(n − k + 1)! k!(n − k + 1)! k!(n − k + 1)!

Mufleh Al-Shatnawi, Ph.D., [Link]., 76

Pascal’s Triangle Pascal’s identity is the basis for a geometric
arrangement of the binomial coefficients in a triangle

each n - th row, binomial coefficients

 n + 1  n   n 
  =   +  
 k   k − 1  k 

 n + 1  n   n 
 k  =  k − 1 +  k 
     

Mufleh Al-Shatnawi, Ph.D., [Link]., 77

Classroom Exercise
Here are the rules for a valid phone number:
1)The first three digits must all be different.
2) The first digit can not be a 1.
3) If the first digit is a 5, the last four digits must all be the same.
How many different phone numbers are possible using
the above rules

Mufleh Al-Shatnawi, Ph.D., [Link]., 78

References
Kenneth H. Rosen. Discrete Mathematics and Its Applications,
Eighth Edition. McGraw Hill, 2019. The textbook is required.
[Link]
crete_Mathematics
[Link] [look for EECS
1028]

Mufleh Al-Shatnawi, Ph.D., [Link]., 79