Chapter 06 - Counting

Counting

The Basics of Counting

Counting problems arise throughout mathematics and computer science. For example, we must count the successful outcomes of experiments and all the possible outcomes of these experiments to determine probabilities of discrete events. We need to count the number of operations used by an algorithm to study its time complexity.

Basic Counting Principles

We first present two basic counting principles, the product rule and the sum rule.

• The Product Rule : Suppose that a procedure can be broken down into a sequence of two tasks. If there are ways to do the first task and for each of these ways of doing the first task, there are ways to do the second task, then there are ways to do the procedure.
• 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.

The sum rule can be phrased in terms of sets as: If are pairwise disjoint finite sets, then the number of elements in the union of these sets is the sum of the numbers of elements in the sets. To relate this to our statement of the sum rule, note there are ways to choose an element from for . Because the sets are pairwise disjoint, when we select an element from one of the sets , we do not also select an element from a different set . Consequently, by the sum rule, because we cannot select an element from two of these sets at the same time, the number of ways to choose an element from one of the sets, which is the number of elements in the union, is This equality applies only when the sets in question are pairwise disjoint.

Suppose that a task can be done in one of two ways, but some of the ways to do it are common to both ways. In this situation, we cannot use the sum rule to count the number of ways to do the task. To correctly count the number of ways to do the two tasks, we must subtract the number of ways that are counted twice. This leads us to an important counting rule.

• The Subtraction Rule : If a task can be done in either ways or 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 subtraction rule is also known as the principle of inclusion–exclusion, especially when it is used to count the number of elements in the union of two sets.

The Pigeonhole Principle

The pigeonhole principle is also called the Dirichlet drawer principle, after the nineteenth century German mathematician G. Lejeune Dirichlet, who often used this principle in his work.

• Theorem : Pigeonhole Principle If is a positive integer and or more objects are placed into boxes, then there is at least one box containing two or more of the objects.
• Corollary : A function from a set with or more elements to a set with elements is not one-to-one.

The Generalized Pigeonhole Principle

• Theorem : The Generalized Pigeonhole Principle If objects are placed into boxes, then there is at least one box containing at least objects.

Permutations and Combinations

Many counting problems can be solved by finding the number of ways to arrange a specified number of distinct elements of a set of a particular size, where the order of these elements matters.

Permutations

A permutation of a set of distinct objects is an ordered arrangement of these objects. An ordered arrangement of elements of a set is called an -permutation. The number of -permutations of a set with elements is denoted by . We can find using the product rule.

• Theorem : If is a positive integer and is an integer with , then there are -permutations of a set with distinct elements.
• Corollary : If and are integers with , then .

Combinations

An -combination of elements of a set is an unordered selection of elements from the set. Thus, an -combination is simply a subset of the set with elements. The number of -combinations of a set with distinct elements is denoted by . Note that is also denoted by and is called a binomial coefficient.

• Theorem : The number of -combinations of a set with elements, where is a nonnegative integer and is an integer with , equals

• Corollary : Let and be nonnegative integers with . Then .

• Definition : A combinatorial proof of an identity is a proof that uses counting arguments to prove that both sides of the identity count the same objects but in different ways or a proof that is based on showing that there is a bijection between the sets of objects counted by the two sides of the identity. These two types of proofs are called double counting proofs and bijective proofs, respectively.

Binomial Coefficients and Identities

As we remarked previously, the number of -combinations from a set with elements is often denoted by . This number is also called a binomial coefficient because these numbers occur as coefficients in the expansion of powers of binomial expressions such as .

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 .

• Theorem : The Binomial Theorem Let and be variables, and let be a nonnegative integer. Then

• Corollary : Let be a nonnegative integer. Then

• Corollary : Let be a positive integer. Then

• Corollary : Let be a nonnegative integer. Then

Identities Involving Binomial Coefficients

• Theorem : Pascal’s Identity Let and be positive integers with . Then
• Theorem : Vandermonde’s Identity Let and be nonnegative integers with not exceeding either or . Then
• Corollary : Let be a nonnegative integer. Then
• Theorem : Let and be a nonnegative integers with . Then

Generating Permutations and Combinations

Any set with elements can be placed in one-to-one correspondence with the set . We can list the permutations of any set of n elements by generating the permutations of the smallest positive integers and then replacing these integers with the corresponding elements.

• Algorithm : Generating the Next Permutation in Lexicographic Order. procedure (: permutation of {} not equal to ) while { is the largest subscript with } while { is the smallest integer greater than to the right of } interchange and while interchange and {this puts the tail end of the permutation after the th position in increasing order} { is now the next permutation}

• Algorithm : Generating the Next -Combination in Lexicographic Order. procedure (: proper subset of not equal to with ) while for to { is now the next combination}