CMSC 250: Combinatorics
Justin Wyss-Gallifent
November 16, 2021
1 The Multiplication Rule for Multiple Events . . . . . . . . . . . . 3
1.1 Introductory Example . . . . . . . . . . . . . . . . . . . . 3
1.2 General Rule . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 The Addition Rule for Disjoint Events . . . . . . . . . . . . . . . 3
2.1 Introductory Example . . . . . . . . . . . . . . . . . . . . 3
2.2 General Rule . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 The Subtraction Rule for Complements of Events . . . . . . . . . 4
3.1 Introductory Example . . . . . . . . . . . . . . . . . . . . 4
3.2 General Rule . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4 Permutations of k Objects out of n Distinct With Replacement . 5
4.1 Introductory Example . . . . . . . . . . . . . . . . . . . . 5
4.2 General Rule . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.3 Basic Examples . . . . . . . . . . . . . . . . . . . . . . . . 5
5 Permutations of k Objects out of n Distinct . . . . . . . . . . . . 5
5.1 Introductory Example . . . . . . . . . . . . . . . . . . . . 5
5.2 General Rule . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.3 Basic Examples . . . . . . . . . . . . . . . . . . . . . . . . 6
5.4 Sneaky Examples . . . . . . . . . . . . . . . . . . . . . . . 6
6 Combinations of k Objects out of n Distinct . . . . . . . . . . . . 7
6.1 Introductory Example . . . . . . . . . . . . . . . . . . . . 7
6.2 General Rule . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3 Basic Examples . . . . . . . . . . . . . . . . . . . . . . . . 8
6.4 Sneaky Examples . . . . . . . . . . . . . . . . . . . . . . . 8
7 Permutations of a Fixed Set with Repeated Elements . . . . . . . 9
7.1 Introduction and Example . . . . . . . . . . . . . . . . . . 9
7.2 General Rule . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.3 Basic Examples . . . . . . . . . . . . . . . . . . . . . . . . 10
7.4 Sneaky Examples . . . . . . . . . . . . . . . . . . . . . . . 10
8 Combinations of k Objects from n Categories . . . . . . . . . . . 11
8.1 Introduction and Example . . . . . . . . . . . . . . . . . . 11
8.2 General Rule . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.3 Basic Examples . . . . . . . . . . . . . . . . . . . . . . . . 12
1
8.4 Sneaky Examples . . . . . . . . . . . . . . . . . . . . . . . 13
9 Mix-N-Match of the Above . . . . . . . . . . . . . . . . . . . . . 13
2
1 The Multiplication Rule for Multiple Events
1.1 Introductory Example
Suppose we flip a coin and also roll a die. There are two possibilities for the
coin, H and T . There are six possibilities for the die, 1, 2, 3, 4, 5, and 6.
Suppose we do both and call each paired result a possibility. How many possi-
bilities are there all together?
Clearly there are twelve. We can think of them as the following pairs:
(H, 1), (H, 2), (H, 3), (H, 4), (H, 5), (H, 6), (T, 1), (T, 2), (T, 3), (T, 4), (T, 5), (T, 6)
1.2 General Rule
Suppose there are k events. If event k has nk possible outcomes then if all k
of the events occur then the total number of possible outcomes is the product
n1n2…nk.
1.3 Examples
Example 1.1. If we roll two different dice then there are 6 · 6 = 36 possible
outcomes.
�
Example 1.2. If we flip two different coins and roll one die then there are
2 · 2 · 6 = 24 possible outcomes.
�
2 The Addition Rule for Disjoint Events
2.1 Introductory Example
Suppose now we get to either flip a coin or roll a die, but not both. Now how
many possibilities are there?
Clearly there are just eight:
H,T, 1, 2, 3, 4, 5, 6
2.2 General Rule
Suppose there are k events. If event k has nk possible outcomes then if exactly
one of the k events occur then the total number of possible outcomes is the sum
n1 + n2 + … + nk.
3
2.3 Examples
Example 2.1. If we have a red die and a green die but we only get to roll one
of them then there are 6 + 6 = 12 possible outcomes.
�
Example 2.2. Suppose there are n buckets labeled 1, 2, …, n. In bucket i
there are i items. We get to select one item from one bucket. How many ways
can we do this? Well, in total the number of possibilities will be:
1 + 2 + … + n =
n(n + 1)
2
�
3 The Subtraction Rule for Complements of Events
3.1 Introductory Example
Suppose we get to roll two distinct dice. How many possibilities will yield a
sum of 10?
The approach here is to note that there are 6 · 6 = 36 total possibilities and of
those it’s easy to identify those which do yield a sum of 10:
6 + 4, 5 + 5, 4 + 6
Thus the total number which do not is just:
36− 3 = 33
3.2 General Rule
Suppose there are N possibilities and we are interested in those which fulfill
some criteria. If k of them do not fulfill that criteria then N − k of them do.
3.3 Examples
Example 3.1. Suppose we flip five coins in a row. How many of them don’t
start with HH?
Well there are 2 ·2 ·2 ·2 ·2 = 32 possibilities all together. Of these, the ones that
start with HH look like HH??? and there are 2 · 2 · 2 = 8 of these. Therefore
there are 32− 8 = 24 ones which don’t start with HH.
�
4
4 Permutations of k Objects out of n Distinct
With Replacement
This is worth mentioning even though it’s just an application of the multiplica-
tion rule.
4.1 Introductory Example
Suppose a box contains pieces of paper with the digits 0, 1, 2, 3, 4. Three times
in a row we draw out a digit and write them down in order, replacing the paper
after each digit.
How many possibilities are there?
Clearly there are 5 choices for each draw and we do this three times, yielding
5 · 5 · 5 possibilities.
4.2 General Rule
Suppose we have n distinct objects and we select k of them, replacing them
after each selection, and we put them in the order we selected them. Then the
number of possibilities is:
nk
This is called a permutation.
4.3 Basic Examples
Example 4.1. How many three-digit hexadecimal numbers are there?
Well, writing down a three-digit hexadecimal number means picking one of
0, 1, …, 9, A,B, …, F three times, with replacement. The number of possibilities
is:
163 = 4096
�
5 Permutations of k Objects out of n Distinct
5.1 Introductory Example
Suppose we have five kittens and wish to select three of them and place them
in order. When order matters this is called a permutation. In this case imagine
three positions into which the kittens will go.
• Into the first position we have 5 kittens to choose from.
• Into the second position we have 4 kittens to choose from.
5
• Into the third position we have 3 kittens to choose from.
Since we are making all of these choices, the total number of possibilities is:
5 · 4 · 3 = 60
5.2 General Rule
Suppose we have n distinct items and wish to select k of them and place them
in order. We say we are permuting k out of n items, or just “n permute k”.
The total number of possibilities is:
P (n, k) =
n!
(n− k)!
Note 5.2.1. This is sometimes denoted nPk.
�
Note 5.2.2. If we’re permuting all of them then k = n and this is just n!.
�
5.3 Basic Examples
Example 5.1. The number of ways to permute 5 out of 7 objects is:
P (7, 5) =
7!
(7− 5)!
=
7!
2!
= 2520
�
Example 5.2. The number of ways to permute 5 objects is:
P (5, 5) = 5! = 120
�
5.4 Sneaky Examples
Example 5.3. Suppose there are 7 people and a round table with 5 seats. We
wish to seat 5 of the people. While the relative position of the people matter,
the absolute position does not. How many ways can we do this?
The approach here is to first ignore the fact that the absolute position does
not matter and just imagine we’re positioning people at the table. There are
P (7, 5) = 2520 ways to do this. Now then, those 2520 can be grouped into
groups of 5 where each group of 5 contains the same relative arrangement (the
5 rotations).
Therefore all together there are 2520/5 = 504 possibilities.
6
�
Example 5.4. How many ways are there to permute the letters in PYTHON
if the P and Y cannot be adjacent?
The approach here is to note that there are P (6, 6) ways to permute all of the
letters and then count and subtract the total number of ways in which they are
together.
• If they are adjacent in the order PY then there are five ways this could
happen:
PY????, ?PY???, ??PY??, ???PY?, and ????PY
However for each of these there are four other letters to permute in the
four remaining positions, so each has 4! possibilities. Thus there are 5(4!)
possibilities which look like these.
• If they are adjacent in the order YP then there are five ways this could
happen:
YP????, ?YP???, ??YP??, ???YP?, and ????YP
However again for each of these there are four other letters to permute in
the four remaining positions, so each has 4! possibilities. Thus there are
5(4!) possibilities which look like these.
Thus all together the number of possibilities is:
P (6, 6)− 5(4!)− 5(4!) = 720− 120− 120 = 480
�
6 Combinations of k Objects out of n Distinct
6.1 Introductory Example
Suppose we have five kittens and wish to select three of them and place them
in a box. Don’t worry, it’s a large box, they have toys, and they’re on their way
to a good home.
When order does not matter this is called a combination. How many possible
ways are there to do this?
The approach to finding a general rule is like the table example from the previous
section. First let’s consider if the order did matter. Then it’s just P (5, 3).
However imagine now that certain permutations of kittens would be considered
the same because we don’t care about order. For example for kittens 1,2,5 we
would have:
7
{1, 2, 5} = {1, 5, 2} = {2, 1, 5} = {2, 5, 1} = {5, 1, 2} = {5, 2, 1}
We see that all of the P (5, 3) permutations can be grouped into groups of 3!
where each group of 3! contains the same collection.
Therefore all together the total number of possibilities is:
P (5, 3)
3!
Notice that:
P (5, 3)
3!
= P (5, 3) ·
1
3!
=
5!
(5− 3)!
·
1
3!
=
5!
(5− 3)!3!
6.2 General Rule
Suppose we have n distinct items and wish to select k of them and place them
together where order does not matter. We say we are choosing k out of n items,
or just “n choose k”.
The total number of possibilities is:
C(n, k) =
n!
(n− k)!k!
Note 6.2.1. This is sometimes denoted nCk or
(
n
k
)
.
�
6.3 Basic Examples
Example 6.1. The number of ways to choose 5 out of 7 objects is:
C(7, 5) =
7!
(7− 5)!5!
=
7!
2!5!
= 21
�
6.4 Sneaky Examples
Consider these more challenging examples.
Example 6.2. Suppose we have 12 people and wish to choose a team of 7.
Order does not matter but there’s an issue. Two of the people have stated that
they must stick together, meaning they’re either both on the team or both not.
How many possibilities are there?
The approach here is to divide the possibilities into two disjoint sets, those with
the two people and those without.
8
• If the two people are on the team then we only need to choose 5 more
people out of the remaining 10 and there are C(10, 5) ways to do this.
• If the two people are not on the team then we need to choose 7 people out
of the remaining 10 and there are C(10, 7) ways to do this.
Since we only get to do one of these we add.
The total number of possibilities is then:
C(10, 5) + C(10, 7) =
10!
(10− 5)!5!
+
10!
(10− 7)!7!
= … = 372
�
7 Permutations of a Fixed Set with Repeated
Elements
7.1 Introduction and Example
Suppose we wish to permute the letters in the word BABAR keeping in mind
that the two As and the two Bs are indistinguishable. How many possibilities
are there?
This is a permutation question (order matters) but we have repeated elements.
The appoach here is to imagine that we have five positions which we wish to fill
with the letters B, A, B, A, and R.
First let’s choose where to put the Bs. We need to choose two positions out of
the five and there are C(5, 2) ways to do this. Notice that since we’re choosing
positions the order does not matter, since for example choosing positions 1,4
and putting a B in each is the same as choosing positions 4,1 and putting a B
in each.
Second let’s choose where to put the As. We need to choose two positions out
of the remaining three and there are C(3, 2) ways to do this.
Third let’s choose where to put the R. There’s really no choice at all but we
could say that we need to choose one position out of the remaining one and
there are C(1, 1) ways to do this.
Since we do all of these, the total number of possibilities is then:
C(5, 2)C(3, 2)C(1, 1)
Notice that as a calculation this simplifies:
C(5, 2)C(3, 2)C(1, 1) =
5!
(5− 2)!2!
·
3!
(3− 2)!2!
·
1!
(1− 1)!1!
=
5!
3!2!
·
3!
1!2!
·
1!
0!1!
=
5!
2!2!1!
9
7.2 General Rule
Suppose we wish to permute n items which are of k types and:
• n1 of one type
• n2 of another type
• …
• nk of the last type
The number of distinguishable permutations is:
n!
n1!n2!…nk!
7.3 Basic Examples
Example 7.1. How many distinct binary strings of length twelve containing
eight 1s are there?
Here we are permuting 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0.
Thus n = 12, n1 = 8 and n2 = 4.
The total number of possibilities is then:
12!
8!4!
= .. = 495
�
Example 7.2. Our local pizza shop has plain, mushroom, and bacon slices. We
are hungry and want 8 slices of pizza, specifically we want 4 plain, 3 mushroom,
and 1 bacon. The order in which we eat these is important, however. How many
possibilities are there?
Here we are permuting P, P, P, P,M,M,M,B.
Thus n = 8, n1 = 4, n2 = 3 and n3 = 1.
The total number of possibilities is then:
8!
4!3!1!
= … = 280
�
7.4 Sneaky Examples
Example 7.3. We are back at our local pizza shop the next day. Today,
however, we’re not sure. We could either have 4 plain, 3 mushroom, and 1
bacon (just like yesterday) or we could have 4 each of mushroom and bacon.
How many possibilities are there?
10
First we have to decide which option we’re going with. There are two and they
are disjoint so we will find the number of possibilities for each and add.
The first option is as the previous question, permuting P, P, P, P,M,M,M,B
so there are 280 possibilities.
The second option is permuting M,M,M,M,B,B,B,B.
Thus n = 8, n1 = 4, and n2 = 4.
Thus for this option the total number of possibilities is then:
8!/(4!4!)
The total number of possibilities is then:
8!
4!3!1!
+
8!
4!4!
= … = 350
�
Example 7.4. Back at the pizza shop for the third day in a row again we want
4 plain, 3 mushroom, and 1 bacon but we don’t want all 4 plain in a row. How
many possibilities are there now?
We know from earlier that there are 280 possibilitie permutations if we don’t
care about whether we have 4 plain in a row or not. Let’s calculate the total
number that would have 4 plain in a row and subtract.
This could happen 5 disjoint ways:
PPPP????, ?PPPP???, ??PPPP??, ???PPPP?, and ????PPPP
However each of these involves four unknowns and each of those is permuting
M,M,M,B and so n = 4, n1 = 3, and n2 = 1, so each has 4!/(3!1!) possibilities
and there are five of them.
Thus in total the number of possibilities is:
280− 5
(
4!
3!1!
)
= … = 240
�
8 Combinations of k Objects from n Categories
8.1 Introduction and Example
Suppose we want 7 sodas. The store has 3 types (and infinitely many of each).
Since we’re just putting them in a bag and taking them home, order does not
matter. How many possibilities are there?
11
The approach to developing a formula for this is rather interesting. We imagine
a soda as an X and a divider as a vertical line |. Because there are three types
of sodas we’ll use two vertical lines. So for example:
XX|XXX|X means two sodas from the first type, three sodas from the
second type, and one soda from the first type.
and
XXXX|XXX| means four sodas from the first type, three sodas from the
second type, and no sodas from the third type.
and
||XXXXXXX means no sodas from the first type, no sodas from the second
type, and seven sodas from the third type.
Think about this as a permutation of 7 + 2 items of which 7 are in one category
(the Xs) and 2 are in the second category (the |s).
We know that the number of ways to do this is:
(7 + 2)!
7!2!
Notice that this is equal to C(7 + 3− 1, 7).
8.2 General Rule
Suppose we take a combination of n object from k categories. The number of
ways this can be done equals:
C(n + k − 1, n)
8.3 Basic Examples
Here are some more examples:
Example 8.1. We’re having a party and need to buy paper hats. We need 20
paper hats and they come in four colors. How many possible ways could we buy
the hats?
Here we are taking a combination of n = 20 objects from k = 4 categories so
the total number of possibilities is:
C(20 + 4− 1, 20) = C(23, 20) =
20!
(23− 20)!20!
= … = 171
�
12
8.4 Sneaky Examples
Here is one that is a bit more sneaky.
Example 8.2. Because of a terrible scheduling conflict we have two parties to
organize in one day. For the first party we need to choose 20 paper hats from 3
different colors and for the first party we need to choose 10 paper hats from 4
different colors.
Here we are making both choices (two parties!). The first has C(20 + 3− 1, 20)
and the second has C(10 + 4− 1, 10).
Thus the total number of possibilities is:
C(22, 20)C(13, 10) =
22!
(22− 20)!20!
·
13!
(13− 10)!10!
= … = 66066
�
9 Mix-N-Match of the Above
Here are some examples which will really require us to put everything together.
Example 9.1. We are trying to set up a panel discussion and we need 5 faculty
members at a round table. There are 11 faculty members to choose from.
Unfortunately two specific ones are annoying and if they’re both at the table
then they will insist that another specific third one is not. Absolute position
doesn’t matter but relative position does. How many possibilities are there?
First we ignore the rotations of the table and divide the problem into disjoint
cases:
• The annoying two are both on the panel. In this case we need 3 more
faculty members but we can’t have the third one so we only have 11−3 = 8
to choose from so C(8, 3) possibilities. Once we have chosen them we
can permute them around the table 5! ways each so there are C(8, 3)5!
possibilities.
• The first of the annoying ones is on the panel but the second is not. In
this case we need 4 more faculty members but we can’t have the second
annoying one so we only have 11 − 2 = 9 to choose from so P (9, 4) pos-
sibilities. Once we have chosen them we can permute them around the
table 5! ways each so there are C(9, 4)5! possibilities.
• The second of the annoying ones is on the panel but the first is not. Again
there are P (9, 4)5! possibilities.
• Neither of the annoying ones is on the panel. In this case we need 5 faculty
members and we have 9 to choose from so P (9, 5) possibilities. Once we
have chosen them we can permute them around the table 5! ways each so
there are C(9, 5)5! possibilities.
13
Adding these together and then grouping them to account for rotations being
identical the total number of possibilities is:
C(8, 3)5! + C(9, 4)5! + C(9, 4)5! + C(9, 5)5!
5
= … = 10416
�
14
The Multiplication Rule for Multiple Events
Introductory Example
General Rule
Examples
The Addition Rule for Disjoint Events
Introductory Example
General Rule
Examples
The Subtraction Rule for Complements of Events
Introductory Example
General Rule
Examples
Permutations of k Objects out of n Distinct With Replacement
Introductory Example
General Rule
Basic Examples
Permutations of k Objects out of n Distinct
Introductory Example
General Rule
Basic Examples
Sneaky Examples
Combinations of k Objects out of n Distinct
Introductory Example
General Rule
Basic Examples
Sneaky Examples
Permutations of a Fixed Set with Repeated Elements
Introduction and Example
General Rule
Basic Examples
Sneaky Examples
Combinations of k Objects from n Categories
Introduction and Example
General Rule
Basic Examples
Sneaky Examples
Mix-N-Match of the Above