Problem 7
How many ways are there to deal a hand of five cards to two players from a deck of cards (52)?

The order of the five cards doesn’t matter, so this is a combinations problem and not a permutation problem. By the Rule of Product we multiply the number of ways to deal a hand to each player together. The first player chooses 5 cards from the 52 in the deck. The second player chooses 5 cards from the remaining 47 in the deck. 

C(52, 5) \cdot C(47, 5)

\frac{52!}{\cancel{47!} \cdot5!} \cdot \frac{\cancel{47!}}{42! \cdot5!} = 3,986,646,103,440

 

Problem 8
A group of friends composed of Henry, Breonn, Jodi, Rich, Brandon, Scurvy, and Kat need to select four players for a video game at a party. How many ways are there to select the four players if Henry and Kat, or both, are included?

Let P_{1} represent the set of selections where Henry is included and let P_{2} represent the set of selections where Kat is included. Since P_{1} and P_{2} are not disjoint sets (both Henry and Kat could be in the same set), we can’t use the Rule of Sum.

First we count the number of ways Henry can be included, set P_{1}. He can be assigned a spot in four ways from the four open video game spots. The second spot can be chosen from the remaining six people. The third spot can be chosen from the remaining five people, and the fourth spot can be chosen from the remaining four people. So, by the Rule of Product, the number of ways Henry can be selected into a spot among the four players is

P_{1} = 4 \cdot 6 \cdot 5 \cdot 4 = 480

This same selection process applies to Kat.

P_{2} = 480

Now we have to compute the number of ways Henry and Kat are both included to play the game. Henry can be placed into any of the four positions and Kat can be placed into any of the remaining three spots. The third spot can be selected from the remaining five players, and the fourth spot can be chosen from the remaining four people. This comes out to be

|P_{1} \cap P_{2}| = 4 \cdot 3 \cdot 5 \cdot 4 = 240

By the Inclusion-Exclusion Principle

|P_{1} \cup P_{2}| = |P_{1}| + |P_{2}| - |P_{1} \cap P_{2}| = 480 + 480 - 240 = 720

There are 720 ways that Henry, Kat, or both can be selected.

Problem 4
A traveling politician has to visit four cities in the state, in a specific order, but there are nine possible cities to choose from. In this problem order matters, so this is a permutation solution. How many ways are there to travel among four of the nine cities?

P(9, 4) = \frac{9!}{(9 -4)!} = \frac{9!}{5!} = \frac{9 \cdot 8 \cdot 7 \cdot 6 \cdot \cancel{5!}}{\cancel{5!}} = 3024

 

Problem 5
How many ways are there to form a new local charity committee if the committee consists of three local business owners and four community volunteers, if there are seven business owners and nine community volunteers to choose from?

So, we need to select three people from seven business owners, and four people from nine community volunteers. Order doesn’t matter, so these are not permutation problems, they are combination problems.

By the Rule of Product, the total number of ways to form a committee is 3-combinations of a set with 7 elements, multiplied by 4-combinations of a set of 9 elements.

C( 7, 3 ) \cdot C( 9, 4 ) = {7\choose 3} \cdot {9\choose 4} = \frac{7!}{3!(7 - 3)!} \cdot \frac{9!}{4!(9 - 4)!} = 35 \cdot 126 = 4,410

 

Problem 6
How many different strings can be made by reordering the letters of the word HORRORS?

This is not a permutation problem since some of the letters are duplicates. The set of letters contains three Rs, two Os, one H, and one S. The three Rs can be placed among the seven positions in C( 7, 3 ) ways. The two Os can be placed among the remaining four positions in C( 4, 2 ). The H can be placed among the remaining two positions in C( 2, 1 ). Finally, the S can be placed in the last singular position in C( 1, 1 ) ways.

By applying the Rule of Product, we can multiply the ways to pick the four letters together to get the answer.

C( 7, 3 ) \cdot C( 4, 2 ) \cdot C( 2, 1 ) \cdot C( 1, 1 )
= {7\choose 3} \cdot {4\choose 2} \cdot {2\choose 1} \cdot {1\choose 1}
= \frac{7!}{3!(7 - 3)!} \cdot \frac{4!}{2!(4 - 2)!} \cdot \frac{2!}{1!(2 - 1)!} \cdot \frac{1!}{1!(1 - 1)!}
= 35 \cdot 6 \cdot 2 \cdot 1 = 420

Problem 1
Telephone numbers in North America follow the North American Numbering Plan (NANP). How many of these telephone numbers exist? The numbering system consists of three parts: a three-digit area code, a three-digit exchange code, and a four-digit subscriber number. The general format of these numbers is NXX NXX XXXX, where N is a digit ranging from 2 to 9 and X is a digit ranging from 0 to 9.

The format of the area code and the exchange code are the same. By the Rule of Product, the total number of these codes are N times X times X, or 8 · 10 · 10, or 800 codes each. The subscriber number is 10^4, or 10,000.

Now we extend the Rule of Product onto these three codes. The total number of telephone numbers is 800 · 800 · 10,000 = 6,400,000,00.

 

Problem 2
A website enforces a password system which mandates eight to twelve characters, one uppercase letter, one lowercase letter, one number, and one special character. The set of special characters includes !, #, $, %, and & for a total of five characters.

By the Rule of Sum, the total number of passwords is P_{8} + P_{9} + P_{10} + P_{11} + P_{12}, where P_{n} is the number of passwords with n characters.

There are 26 ways to choose an uppercase letter, 26 ways to choose a lowercase letter, 10 ways to choose a number, and 5 ways to choose a special character. Therefore, by the Rule of Sum, the total number ways to choose a password character is 26 + 26 + 10 + 5, or 67 character choices. For a password of eight characters, by the Rule of Product we pick a mandatory uppercase letter (26 ways), a mandatory lowercase letter (26 ways), a mandatory number (10 ways), a mandatory special character (5 ways), and then four characters of any type (67 ways each). This comes out to be:
P_{8} = 26 · 26 · 10 · 5 · 26^4 = 15,445,788,800
P_{9} = 26 · 26 · 10 · 5 · 26^5 = 401,590,508,800
P_{10} = 26 · 26 · 10 · 5 · 26^6 = 10,441,353,228,800
P_{11} = 26 · 26 · 10 · 5 · 26^7= 271,475,183,948,800
P_{12} = 26 · 26 · 10 · 5 · 26^8 = 7,058,354,782,668,800
P_{total} = P_{8} + P_{9} + P_{10} + P_{11} + P_{12} = 7,340,688,356,144,000

 

Problem 3
The Internet Protocol version 4 (IPv4) has five classes of IP addresses, Class A, Class B, Class C, Class D, and Class E which are represented by a 32-bit value. How many possible IP addresses exist for Class C? A Class C IP address is composed of three parts. The first part has three static bits, 1, 1, and 0. This is followed by the network part which has 21 bits. Finally, a host part composed of 8 bits. Note that there is no such IP address that has a host part of all zeros, or all ones.

There is one way to select each of the first three bits. Next, there are 2^21 ways to choose the network part. Finally, there are 2^8 ways to choose the host part, but remember that a host part cannot have a bit value of all zeros or all ones, so by the Rule of Difference we will subtract those two bit values from the host part. So, applying the Rule of Product to the three IP address parts, we find that the number of Class C addresses is:
1 · 1 · 1 · 2^{21} · (2^8 - 2) = 2,097,406

A combination¹²³⁴ is similar to a permutation, but order doesn’t matter.

The cardinality of r-combinations
An r-combination is an unordered selection of r elements from a set of n elements and has the notations C( n, r) or n\choose r. Repetition of elements from the selection are not allowed. This number is also known as the binomial coefficient and is stated as “n choose r”.
C( n, r ) = {n\choose r} = \frac{n!}{r!(n - r)!}

Example 1
Given the set of letters {a, b, c}, what is the 2 combination of the set?
This is “3 choose 2”, or C( 3, 2).
C(3, 2) = {3\choose 2} = \frac{3!}{2!(3 - 2)!} = \frac{3!}{2!\cdot1!} = \frac{3\cdot\cancel{2!}}{\cancel{2!}} = 3
Enumerated 2-combination as proof:
a, b
a, c
b, c

Example 2
How many ways are there to choose 3 players from a 10-member chess team to play at a regional tournament?
Order of the three players doesn’t matter here, so this is a combination problem.
C(10, 3) = {10\choose3} = \frac{10!}{3!(10 - 3)!} = \frac{10!}{3!\cdot7!} = \frac{10\cdot9\cdot8\cdot\cancel{7!}}{3!\cdot\cancel{7!}} = \frac{10\cdot9\cdot8}{3\cdot2\cdot1} = \frac{720}{6} = 120
120 ways to select 3 players from a team of 10.

 

What if allowing repetition is needed? In this case the formula for counting the combinations slightly changes. These are r-combinations with repetition, otherwise known as multisets.

The cardinality of r-multisets
An r-multiset is computed as follows
{r + n - 1 \choose r}

 

Example 3
What is the cardinality of the 2-multiset from the set {1, 2, 3}?
{2 + 3 - 1\choose2} = {4\choose2} = \frac{4!}{2!(4 - 2)!} = \frac{4\cdot3\cdot\cancel{2!}}{\cancel2!\cdot2!} = \frac{12}{2\cdot1} = 6
Enumerated 2-multiset results for proof:
1, 1
1, 2
1, 3
2, 2
2, 3
3, 3

Example 4
How many ways are there to select 5 cans of soda from three flavors: orange, root beer, or cola, if there are at least five of each flavor to pick from? In this case r is equal to 5, the number of cans that need to be selected from n, which is equal to 3, the different kinds of soda we can select from.
{5 + 3 - 1\choose 5} = {7\choose 5} = \frac{7!}{5!(7 - 5)!} = \frac{7\cdot6\cdot\cancel{5!}}{\cancel{5!}\cdot2!} = \frac{42}{2\cdot1} = 21

 

 

A permutation¹²³⁴ is a set of elements is every possible ordered arrangement of those elements.

The cardinality of a permutation
The number of permutations in a set of n elements is n factorial, n!

Example 1
Given a set of three chairs placed in a row for Bob, Alice, and Cid, how many permutations are there?
Using the Rule of Product, there are three ways to choose the first chair. With the two people left over, there are two ways to choose the second chair. There is one person left for the third chair. The total number of permutations is 3 · 2 · 1, or 6. Or, using just applying n! mentioned above, 3! or 6.
Enumerated permutations, A for Alice, B for Bob, and C for Cid:
ABC
ACB
BAC
BCA
CAB
CBA

Example 2
How many permutations of the letters ABCDEF contain the substring BCD?
Here we have six letters, but we are constrained by the substring BCD. This leaves us with A, E, and F.
Therefore the total set has four elements: A, BCD, E, and F.
The answer is 4!, or 24.

Now, what if we want the permutations of a set of n elements, where the number of selected elements is less-than the total size of the set. These are called r-permutations²³⁴, or sometimes k-permutations¹.

The cardinality of r-permutations
The ordered selection of r elements taken from a set of n elements is called an r-permutation. The notation for a number of r-permutations taken from a set of of n elements is P( n, r ). This is computed by
P(n, r) = \frac{n!}{(n - r)!}

Example 3
What is the 2-permutation from the set of letters {a, b, c} ?
P(3, 2) = \frac{3!}{(3 -2)!} = \frac{3!}{1!} = \frac{3 \cdot 2 \cdot 1}{1} = 6
Enumerated permutations as proof:
ab
ac
ba
bc
ca
cb

Example 4
A swimming contest has 8 participants and will award a gold, silver, and bronze medal to the three winners. How many ways are there to award the swimmers?
P(8, 3) = \frac{8!}{(8 -3)!} = \frac{8!}{5!} = \frac{8 \cdot 7 \cdot 6 \cdot \cancel{5!}}{\cancel{5!}} = 336

 

The Inclusion-Exclusion Principle¹²⁴, Inclusion/Exclusion Rule³, or similarly named technique is used in counting problems often found in mathematics and computer science. Most all Discrete Mathematics textbooks cover this rule in the topic of counting. This rule serves as a basis for later counting techniques.

As we saw with the Rule of of Sum, when there are different tasks that do not happen at the same time, we are able to add the number of ways to do each task together in order to find the total number of ways there are to perform a task. But, what happens if we need to count the number of ways when both tasks happen at the same time? In this case we can apply the Inclusion-Exclusion Principle.

The Inclusion-Exclusion Principle
If there are n ways of performing a task, and there are m ways of performing a second task, and these tasks are performed at the same time, then the total number of possible ways to perform the task is equal to (n + m) minus the elements they have in common. When n and m are added together, the elements they have in common are counting twice, hence we must subtract these out, once. This is derived from set theory, so the original formula looks like this for two sets of tasks:
N(A \cup B) = N(A) + N(B) - N(A \cap B)
where N() is the number of elements

Note this changes for more than two sets of tasks. Adding up the possible tasks from three sets looks like this:
N(A \cup B \cup C) = N(A) + N(B) + N(C) - N(A \cap B) - N(A \cap C) - N(B \cap C) + N(A \cap B \cap C)

Calculating the total number of possibilities becomes more complex as the number of sets being added together increases.

Example 1
Extending Example 1 from the post on the Rule of Sum, let us amend the original problem. One of the students is a grad student, but they are also an instructor. So, this person is being counted twice, once as a student and once as a faculty member. We need to remove the second count she is included in. So, by the Inclusion-Exclusion Principle we have:
N(A \cup B) = N(A) + N(B) - N(A \cap B)
N(students \cup faculty) = N(students) + N(faculty) - N(students \cap faculty)
N(A \cup B) = 63 + 7 - 1
From this, we know that the total number of ways to select a person for the vacancy is 69.

Example 2
How many bit strings of length 4 begins with a 11 or end with a 0?
The first criteria is to have a string that starts with a 11. From the the Rule of Product we know that there is one way to pick the first bit, 1, and one way to pick the second bit, 1. There are 2 ways to pick the third bit and 2 ways to choose the fourth bit, or 1 · 1 · 2 · 2, or 4 possible strings.
The second criteria is to choose a string that ends with a 0. From the the Rule of Product we know that there 2 ways to pick the first bit, 2 ways to pick the second bit, 2 ways to pick the third bit and 1 way to choose the fourth bit, 0, or 2 · 2 · 2 · 1, or 8 possible strings.
In this case we cannot apply the Rule of Sum as there is only one task, selecting a string that either starts with 11 or ends with a 0. 
To better understand this, all strings starting with 11 are enumerated below:

0011
0111
1011
1111

And all the strings ending with 0 are enumerated below:

0000
0001
0010
0011
0100
0101
0110
0111

So, we can see the first set has 4 possibilities, and the second set has 8 possibilities. But look at the two sets, there are duplicates. Both 0011 and 0111 are shared between the sets. We don’t want to count them twice, so we will subtract these duplicates once to get the correct value. By the Inclusion-Exclusion Principle we know the total number of bit strings that start with 11 or end with a 0 is equal to N(A \cup B).
N(A \cup B) = 4 + 8 - 2
So, there are 10 strings that meet the original criteria.

 

 

The Rule of Difference, Difference Rule¹ ,  or similarly named technique is used in counting problems often found in mathematics and computer science. Not all Discrete Mathematics textbooks cover this rule in the context of counting as it is simple and intuitive. This rule serves as a common technique used in counting problems.

The Rule of Difference
Given a set of items T with a subset A, the number of items not in subset A, named subset B, is equal to the number of items in set T minus the number of items in subset A.
N(B) = N(T) - N(A)

Example 1
Extending Example 1 from the post on the Rule of Sum, out of a total school population of 900 (students and faculty), how many people are not eligible to join the school committee?
The result of the original problem showed that 70 people were eligible for joining the school committee. So, we have the total set T of 900 people, and subset A of 70 eligible people.
By the Rule of Difference,
N(T) - N(A) = N(B)
900 - 70 = 830
830 people are not eligible to join the school committee.

Example 2
Extending Example 1 from the post on the Rule of Product, out of 300 parking spots, the ones not labeled will be designated for guest parking. How many guest parking spots will there be?
The result of the original problem showed that there will be a total of 260 labeled parking spots. So, we have the total set T of 300 parking spots, and a subset A of 260 labeled parking spots.
By the Rule of Difference,
N(T) - N(A) = N(B)
300 - 260 = 40
There will be 40 guest parking spots.

The Rule of Product¹ , Product Rule² , Multiplication Rule³, or similarly named technique is used in counting problems often found in mathematics and computer science. Most all Discrete Mathematics textbooks cover this rule in the topic of counting. This rule serves as a basis for later counting techniques.

The Rule of Product
If there is a main task that can be broken down into two subtasks, and there are n ways of performing one of the subtasks, and there are m ways of performing the other subtask, then there are n · m possible ways to choose how to perform the main task.

Example 1
A parking lot is labeling their parking spaces with a single letter of the alphabet, and a single digit. How many parking spots will this labeling scheme cover?

The main task of labeling a parking spot consists of two substaks, picking one of the 26 letters of the alphabet and picking one of the 10 digits.

By the Rule of Product there are 26 · 10, or 260 parking spots that can be labeled.

Example 2
How many possible bit strings are there in a single byte?

There are 8 bits in a byte, and each bit has two states, 1 or 0. By the Rule of Product, there are 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2, or 2^8, or 256 possible bits strings in a byte.

Example 3
A state license plate labeling scheme is being updated. Each plate will have six characters. The first three characters may be either letters or digits. The remaining three characters may be digits. How many possible license plates can be produced using this labeling scheme?

The first, second, and third characters have 26 letter possibilities plus 10 digit possibilities, for a total of 36 possibilities for each character. The fourth, fifth, and sixth characters of the plate have 10 possible digits each. By the Rule of Product there are 36 · 36 · 36 · 10 · 10 · 10, or 36^3 \cdot 10^3, or 46,656,000 possible plates.

 

The Rule of Sum¹ , Sum Rule² , Addition Rule³, or similarly named technique is used in counting problems often found in mathematics and computer science. Most all Discrete Mathematics textbooks cover this rule in the topic of counting. This rule serves as a basis for later counting techniques.

The Rule of Sum
If there are n ways of performing a task, and there are m ways of performing a second task, and these tasks cannot be done at the same time, then there are n + m possible ways to choose how to perform one of these tasks.

Example 1
A school committee needs to fill to fill a vacancy for a representative from one of two groups:

• • a computer science faculty member
  • a computer science student

There are 7 computer science faculty, and 63 computer science students. These two groups are mutually exclusive, there is no one who is both a student and faculty.
So, there are 7 ways to choose a computer science faculty member. There are 63 ways to pick a student. When the Rule of Sum is applied, there are 7 + 63, or 70 ways to choose a representative.

Example 2
The Rule of Sum can be extended to more than two sets of choices. Example 1 from above can be amended to allow a third group of people, the electrical engineering faculty which consists of 8 people.
After applying the Rule of Sum to this new problem, there are 7 + 63 + 8, or 78 possible ways to choose a representative.

Example 3
An English student may select a topic for a final essay from four separate categories. The first category has three choices, the second category has four choices, the third category has three choices, and the fourth category has five choices.
By applying the Rule of Sum, the English student has 3 + 4 + 3 + 5, or 15 topic choices.

Example 4
A person decides to go shopping at a single store, to either the east side of town, or the west side of town. The east side of town has an electronics store and a game store. The west side of town has a candy store, a book store, and a hobby store. So, there are two ways to pick a store on the east side of town, and three choices on the west side of town.
By applying the Rule of Sum, there are 2 + 3, or 5 total stores to choose from.