# Counting

Introduction

Combinatorics: Study of arangement of objects.
Enumeration: Counting of objects with certain properties.

Say we have a set of objects with certain properties.
Counting is used to determine the number of these objects.

The Basics of Counting

Counting problems arise throughout mathematics and computer science.
Examples:
1. The successful outcomes of experiments.
2. The number of operations used by an algorithm: its time complexity.

Basic Counting Principles

There are two basic counting principles.

The Product Rule

The Product Rule
Suppose that a procedure can be broken into two parts, and there are n1 ways to do the first part, and n2 ways to do the second (and the choices for the two parts are independent). Then there are n1n2 ways to do the task.

Examples:
1. 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?

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.

2. How many different license plates can be made if each plate contains a sequence of three uppercase English letters followed by three digits (and no sequences of letters are prohibited, even if they are obscene)?

There are 26 choices for each of the three uppercase English letters and ten choices for each of the three digits. Hence, by the product rule there are a total of
26 * 26 * 26 * 10 * 10 * 10 = 17,576,000 possible license plates.

The Sum Rule

The Sum Rule
If a task can be done in either one of n1 ways or one of n2 ways, then it can be done in n1 + n2 ways.

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

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.

2.What is the value of k after the following code, where n1, n2, . . . , nm are positive integers, has been executed?

The initial value of k is zero. This block of code is made up of m different loops. Each time a loop is traversed, 1 is added to k. To determine the value of k after this code has been executed, we need to determine how many times we traverse a loop. Note that there are ni ways to traverse the ith loop. Because we only traverse one loop at a time, the sum rule shows that the final value of k, which is the number of ways to traverse all of the m loops is:
n1 + n2 + ... + nm

More Complex Counting Problems

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?

Let P be the total number of possible passwords, and let P6, P7, and P8 denote the number of possible passwords of length 6, 7, and 8, respectively.
By the sum rule, P = P6 + P7 + P8.
We will now find P6 , P7, and P8.
Finding P6 directly is difficult. To find P6 it is easier to find the number of strings of uppercase letters and digits that are six characters long, including those with no digits, and subtract from this the number of strings with no digits. By the product rule, the number of strings of six characters is 366, and the number of strings with no digits is 266. Hence,
P6 = 366 - 266 = 2,176,782,336 - 308,915,776 = 1,867,866,560.
Similarly, we have
P7 = 367 - 267 = 78,364,164,096 - 8,031,810,176 = 70,332,353,920
and
P8 = 368 - 268 = 2,821,109,907,456 - 208,827,064,576 = 2,612,282,842,880.
P = P6 + P7 + P8 = 2,684,483,063,360.

The Subtraction Rule (Inclusion-Exclusion for Two Sets)

The Subtraction Rule
If a task can be done in n1 ways or n2 ways, then the number of total ways it can be done is n1 + n2 minus the number of ways common to n1 and n2.

Example:

A computer company receives 350 applications from computer graduates for a job planning a line of new web servers. Suppose that 220 of these applicants majored in computer science, 147 majored in business, and 51 majored both in computer science and in business. How many of these applicants majored neither in computer science nor in business?

To find the number of these applicants who majored neither in computer science nor in business, we can subtract the number of students who majored either in computer science or in business (or both) from the total number of applicants. Let A1 be the set of students who majored in computer science and A2 the set of students who majored in business. Then A1A2 is the set of students who majored in computer science or business (or both), and A1A2 is the set of students who majored both in computer science and in business. By the subtraction rule the number of students who majored either in computer science or in business (or both) equals:
|A1A2| = |A1 | + |A2| - |A1A2| = 220 + 147 - 51 = 316.
We conclude that 350 - 316 = 34 of the applicants majored neither in computer science nor in business.

The Division Rule

The Division Rule
There are n / d ways to do a task when it can be carried out in n ways, and for every way w exactly d of the n ways correspond to w.

Example:
How many different ways are there to seat four people around a circular table, where two seatings are considered the same when each person has the same left neighbor and the same right neighbor?

We arbitrarily select a seat at the table and label it seat 1. We number the rest of the seats in numerical order, proceeding clockwise around the table. Note that are four ways to select the person for seat 1, three ways to select the person for seat 2, two ways to select the person for seat 3, and one way to select the person for seat 4.
Thus, there are 4! = 24 ways to order the given four people for these seats. However, each of the four choices for seat 1 leads to the same arrangement, as we distinguish two arrangements only when one of the people has a different immediate left or immediate right neighbor. Because there are four ways to choose the person for seat 1, by the division rule there are 24/4 = 6 different seating arrangements of four people around the circular table.

Tree Diagrams

Example:
A playoff between two teams consists of at most five games. The first team that wins three games wins the playoff. In how many different ways can the playoff occur?

The tree diagram in Figure 3 displays all the ways the playoff can proceed, with the winner of each game shown. We see that there are 20 different ways for the playoff to occur.

Test Yourself!
1. Which of the following is NOT a basic counting principle?
1. The pigeonhole principle
2. The sum rule
3. The product rule
2. Suppose a procedure can be broken down into two tasks. According to the ‘product rule’, if there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then how many ways are there to do the procedure?
1. n1n2
2. n1 / n2
3. n1 + n2
4. n2 - n1
3. A customer can choose one of 5 monitors, one of 4 keyboards, one of 2 CPUs and one of 3 printers, to buy a computer system. Determine the number of possible systems that the customer can choose from.
1. 121
2. 14
3. 120
4. 15
4. Mona wants to make a list of passwords, with each password containing a sequence of 2 lowercase English alphabets followed by 3 digits. How many different passwords can Mona create?
1. 676,000
2. 6,760
3. 82
4. 80
5. A computer company receives 350 applications from computer graduates for a job planning a line of new Web servers. Suppose that 220 of these applicants majored in computer science, 147 majored in business, and 51 majored both in computer science and in business. How many of these applicants majored neither in computer science nor in business?
1. 29
2. 34
3. 31
4. 35
6. True or False: There are d/n ways to do a task if it can be done using a procedure that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to way w.
1. False
2. True

1. a; 2. a; 3. c; 4. a; 5. b; 6. a;

The Pigeonhole Principle
Introduction

The pigeonhole principle states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with at least two pigeons in it.

Theorem 1

The Pigeonhole Principle
If k is a positive integer and k + 1 objects are to be placed into k boxes, then at least one box must have more than one object in it.

Corollary 1

A function f from a set with k + 1 or more elements to a set with k elements is not one-to-one.

Example:

How many students must be in a 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?

There are 101 possible scores on the final. The pigeonhole principle shows that among any 102 students there must be at least 2 students with the same score.

Generalized Pigeonhole Principle

The pigeonhole principle states that there must be at least two objects in the same box when there are more objects than boxes. However, even more can be said when the number of objects exceeds a multiple of the number of boxes. For instance, among any set of 21 decimal digits there must be 3 that are the same. This follows because when 21 objects are distributed into 10 boxes, one box must have more than 2 objects.

Theorem 2

The Generalized Pigeonhole Principle
If n objects are placed into k boxes, then there is at least one box containing at least ceiling(n / k) objects.

Example:

What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades, A, B, C, D, and F?

The minimum number of students needed to ensure that at least six students receive the same grade is the smallest integer n such that ceiling(n / 5) = 6.
The smallest such integer is n = 5 * 5 + 1 = 26.
If you have only 25 students, it is possible for there to be five who have received each grade so that no six students have received the same grade. Thus, 26 is the minimum number of students needed to ensure that at least six students will receive the same grade.

An Elegant Application of the Pigeonhole Principle

Assume that in a group of six people, each pair of individuals consists of two friends or two enemies. Show that there are either three mutual friends or three mutual enemies in the group.

Test Yourself!
1. If Jimmy has red, blue, yellow and green gloves and if he decides to blindly pull out a few gloves, how many gloves must he pull out to guarantee that he has a pair?
1. 4
2. 3
3. 5
4. Cannot be determined
2. According to the generalized Pigeonhole Principle, if n objects are placed into k boxes, then there is at least one box containing at least ceiling(k/n) objects
1. False
2. True
3. What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades, A, B, C, D, and F?
1. 25
2. 10
3. 6
4. 26
4. How many students must be in a 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?
1. 102
2. 98
3. 100
4. 101
5. The pigeonhole principle states that there must be at least two objects in the same box when there are more objects than boxes.
1. False
2. True

1. c; 2. a; 3. d; 4. a; 5. b;

Permutations and Combinations
Permutations

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.

Theorem 1
Corollary 1
Example 1

How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize winner from 100 different people who have entered a contest?

P (100, 3) = 100 * 99 * 98 = 970,200

Example 2

How many permutations of the letters ABCDEFGH contain the string ABC ?

Because the letters ABC must occur as a block, we can find the answer by finding the number of permutations of six objects, namely, the block ABC and the individual letters D, E, F , G, and H .
Because these six objects can occur in any order, there are 6! = 720 permutations of the s letters ABCDEFGH in which ABC occurs as a block.

Video on permutations and chairs
Combinations

An r-combination of elements of a set is an unordered selection of r elements from the set.
Thus, an r-combination is simply a subset of the set with r elements.
The number of r-combinations of a set with n distinct elements is denoted by C(n, r).
C(n, r) is called a binomial coefficient.

Theorem 2
Corollary 2
Definition 1
Example 1

How many ways are there to select five players from a 10-member tennis team to make a trip to a match at another school?

C(10, 5) = 10! /( 5! * 5!) = 252

Example 2

How many bit strings of length n contain exactly r 1s?

The positions of r 1s in a bit string of length n form an r-combination of the set {1, 2, 3, . . . , n}.
Hence, there are C(n, r) bit strings of length n that contain exactly r 1s..

Test Yourself!
1. A student is taking History, Math, English and Chemistry in her current semester. In how many ways can she schedule her courses if she has room for 5 courses (which means she has a spare)?
1. 120
2. 60
3. 121
4. 125
2. Mia has 4 walls in her house left to paint. Each wall can be painted any color. If 6 different colors of paint are available, how many ways can the walls be painted?
1. 120
2. 180
3. 728
4. 1296
3. An electrician buys a few light bulbs and realizes that 10 are working and 4 are defective. In how many ways can 5 bulbs be selected if only 3 work?
1. 720
2. 120
3. 240
4. 24
4. A jar contains blue marbles, red marbles and green marbles. If 4 marbles are selected at random from the jar, how many unique marble combinations are there?
1. 25
2. 15
3. 20
4. 19
5. The number of diagonals in a pentagon is:
1. 8
2. 7
3. 6
4. 5

1. a; 2. d; 3. a; 4. b; 5. d;

Binomial Coefficients and Identities
The Binomial Theorem

The binomial theorem gives the coefficients of the expansion of powers of binomial expressions.
A binomial expression is simply the sum of two terms, such as x + y.

Binomial Theorem 1
Binomial Corollary 1
Binomial Corollary 2: Not Covered Spring 2018
Binomial Corollary 3: Not Covered Spring 2018
Pascal's Identity and Triangle
Theorem 2
Other Identities Involving Binomial Cooefficients
Not Covered Spring 2018
Theorem 3: Not Covered Spring 2018
Corollary 4: Not Covered Spring 2018
Theorem 4: Not Covered Spring 2018
Generalized Permutations and Combinations
Not covered Spring 2018
Permutations With Repetition
Theorem 1
Example

How many strings of length r can be formed from the uppercase letters of the English alphabet?

By the product rule, because there are 26 uppercase English letters, and because each letter can be used repeatedly, we see that there are 26 r strings of uppercase English letters of length r.
The number of r-permutations of a set with n elements when repetition is allowed is given in Theorem 1.

Combinations with Repetition
Theorem 2
Example

Suppose that a cookie shop has four different kinds of cookies. How many different ways can six cookies be chosen? Assume that only the type of cookie, and not the individual cookies or the order in which they are chosen, matters.

The number of ways to choose six cookies is the number of 6-combinations of a set with four elements.
From Theorem 2 this equals C(4 + 6 - 1, 6) = C(9, 6).
C(9, 6) = C(9, 3) = (9 * 8 * 7) / (1 * 2* 3) = 84
There are 84 different ways to choose the six cookies.

Permutations with Indistinguishable Objects
Theorem 3

Every sequence of n2 + 1 distinct numbers must contain a sequence of length n + 1 that is either strictly increasing or strictly decreasing.

Example

How many different strings can be made by reordering the letters of the word SUCCESS?

Because some of the letters of SUCCESS are the same, the answer is not given by the number of permutations of seven letters. This word contains three Ss, two Cs, one U , and one E.
To determine the number of different strings that can be made by reordering the letters, first note that the three Ss can be placed among the seven positions in C(7, 3) different ways, leaving four positions free.
Then the two Cs can be placed in C(4, 2) ways, leaving two free positions. The U can be placed in C(2, 1) ways, leaving just one position free. Hence E can be placed in C(1, 1) way.
Consequently, from the product rule, the number of different strings that can be made is

Distributing Objects Into Boxes
DISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES

Example:
How many ways are there to distribute hands of 5 cards to each of four players from the standard deck of 52 cards?

Theorem 4

INDISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES

Counting the number of ways of placing n indistinguishable objects into k distinguishable boxes turns out to be the same as counting the number of n-combinations for a set with k elements when repetitions are allowed.
The reason behind this is that there is a one-to-one correspondence between n-combinations from a set with k elements when repetition is allowed and the ways to place n indistinguishable balls into k distinguishable boxes. To set up this correspondence, we put a ball in the ith bin each time the ith element of the set is included in the n-combination.

Example:
How many ways are there to place 10 indistinguishable balls into eight distinguishable bins?

DISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES

Counting the ways to place n distinguishable objects into k indistinguishable boxes is more difficult than counting the ways to place objects, distinguishable or indistinguishable objects, into distinguishable boxes.

Example:
How many ways are there to put four different employees into three indistinguishable offices, when each office can contain any number of employees?

INDISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES

Some counting problems can be solved by determining the number of ways to distribute indistinguishable objects into indistinguishable boxes. We illustrate this principle with an example.

Example:
How many ways are there to pack six copies of the same book into four identical boxes, where a box can contain as many as six books?

Generating Permutations and Combinations
Not covered Spring 2018
Generating Permutations
Algorithm 1
Example

Generate the permutations of the integers 1, 2, 3 in lexicographic order.

Begin with 123. The next permutation is obtained by interchanging 3 and 2 to obtain 132. Next, because 3 > 2 and 1 < 3, permute the three integers in 132. Put the smaller of 3 and 2 in the first position, and then put 1 and 3 in increasing order in positions 2 and 3 to obtain 213. This is followed by 231, obtained by interchanging 1 and 3, because 1 < 3. The next larger permutation has 3 in the first position, followed by 1 and 2 in increasing order, namely, 312.
Finally, interchange 1 and 2 to obtain the last permutation, 321. We have generated the permutations of 1, 2, 3 in lexicographic order.
They are 123, 132, 213, 231, 312, and 321.

Generating Combinations
Algorithm 2
Example

Find the next bit string after 10 0010 0111.

The first bit from the right that is not a 1 is the fourth bit from the right.
Change this bit to a 1 and change all the following bits to 0s. This produces the next larger bit string, 10 0010 1000.

Algorithm 3
Example

Find the next larger 4-combination of the set {1, 2, 3, 4, 5, 6} after {1, 2, 5, 6}.