Chapter 08 - Advanced Counting Techniques

Advanced Counting Techniques

In this chapter, we will see that many counting problems can be solved using formal power series, called generating functions, where the coefficients of powers of represent terms of the sequence we are interested in. Besides solving counting problems, we will also be able to use generating functions to solve recurrence relations and to prove combinatorial identities.

Applications of Recurrence Relations

We can use recurrence relations to model a wide variety of problems, such as finding compound interest, counting rabbits on an island, determining the number of moves in the Tower of Hanoi puzzle, and counting bit strings with certain properties.

Rabbits and the Fibonacci Numbers: Consider this problem, which was originally posed by Leonardo Pisano, also known as Fibonacci, in the thirteenth century. A young pair of rabbits (one of each sex) is placed on an island. A pair of rabbits does not breed until they are 2 months old. After they are 2 months old, each pair of rabbits produces another pair each month. Find a recurrence relation for the number of pairs of rabbits on the island after months, assuming that no rabbits ever die.

Solution: Denote by the number of pairs of rabbits after months. We claim that are the terms of the Fibonacci sequence.

The rabbit population can be modeled using a recurrence relation. At the end of the first month, the number of pairs of rabbits on the island is . Because this pair does not breed during the second month, also. To find the number of pairs after months, add the number on the island the previous month, , and the number of newborn pairs, which equals , because each newborn pair comes from a pair at least months old.

Consequently, the sequence satisfies the recurrence relation for together with the initial conditions and . Because this recurrence relation and the initial conditions uniquely determine this sequence, the number of pairs of rabbits on the island after months is given by the th Fibonacci number.

Parenthesis Problem: Find a recurrence relation for the number of ways to parenthesize the product of numbers, to specify the order of multiplication.

Solution: To develop a recurrence relation for , we note that however we insert parentheses in the product , one "" operator remains outside all parentheses, namely, the operator for the final multiplication to be performed. This final operator appears between two of the numbers, say, and . There are ways to insert parentheses to determine the order of the numbers to be multiplied when the final operator appears between and because there are ways to insert parentheses in the product to determine the order in which these numbers are to be multiplied and ways to insert parentheses in the product to determine the order in which these numbers are to be multiplied. Because this final operator can appear between any two of the numbers, it follows that Note that the initial conditions are and . The sequence is the sequence of Catalan numbers, named after Eugène Charles Catalan.

Algorithms and Recurrence Relations

We conclude this section by introducing another algorithmic paradigm known as dynamic programming, which can be used to solve many optimization problems efficiently.

An algorithm follows the dynamic programming paradigm when it recursively breaks down a problem into simpler overlapping subproblems, and computes the solution using the solutions of the subproblems. Generally, recurrence relations are used to find the overall solution from the solutions of the subproblems. In this section we will illustrate the use of dynamic programming by constructing an algorithm for solving a scheduling problem.

We formalize this problem by supposing that we have talks, where talk begins at time ends at time , and will be attended by students. We want a schedule that maximizes the total number of student attendees. That is, we wish to schedule a subset of talks to maximize the sum of over all scheduled talks. (Note that when a student attends more than one talk, this student is counted according to the number of talks attended.) We denote by the maximum number of total attendees for an optimal schedule from the first talks, so is the maximal number of total attendees for an optimal schedule for all talks.

We first sort the talks in order of increasing end time. After doing this, we renumber the talks so that . We say that two talks are compatible if they can be part of the same schedule, that is, if the times they are scheduled do not overlap (other than the possibility one ends and the other starts at the same time). We define to be largest integer for which , if such an integer exists, and otherwise. That is, talk is the talk ending latest among talks compatible with talk that end before talk ends, if such a talk exists, and if there are no such talks.

To develop a dynamic programming algorithm for this problem, we first develop a key recurrence relation. To do this, first note that if there are two possibilities for an optimal schedule of the first talks (recall that we are assuming that the talks are ordered by increasing end time): (a) talk belongs to the optimal schedule or (b) it does not.

Case : We know that talks do not belong to this schedule, for none of these other talks are compatible with talk . Furthermore, the other talks in this optimal schedule must comprise an optimal schedule for talks . For if there were a better schedule for talks by adding talk we will have a schedule better than the overall optimal schedule. Consequently, in case we have .

Case : When talk does not belong to an optimal schedule, it follows that an optimal schedule from talks is the same as an optimal schedule from talks . Consequently, in case we have .

Combining cases and leads us to the recurrence relation Now we can construct an efficient algorithm for computing the maximum total number of attendees. We ensure that the algorithm is efficient by storing the value of each after we compute it. This allows us to compute only once. If we did not do this, the algorithm would have exponential worst-case complexity. The process of storing the values as each is computed is known as memoization and is an important technique for making recursive algorithms efficient.

• Algorithm: Dynamic Programming Algorithm for Scheduling Talks procedure : start times of talks; : end times of talks; : number of attendees to talks) sort talks by end time and relabel so that

  for to if no job with is compatible with job else and job is compatible with job for to return is the maximum number of attendees

Solving Linear Recurrence Relations

One important class of recurrence relations can be explicitly solved in a systematic way. These are recurrence relations that express the terms of a sequence as linear combinations of previous terms.

• Definition: A linear homogeneous recurrence relation of degree with constant coefficients is a recurrence relation of the form where are real numbers, and .

A consequence of the second principle of mathematical induction is that a sequence satisfying the recurrence relation in the definition above is uniquely determined by this recurrence relation and the initial conditions .

Solving Linear Homogeneous RR with Constant Coefficients

We can use two key ideas to find all solutions of linear homogeneous recurrence relations. First, these recurrence relations have solutions of the form where is a constant.

We claim is a solution of the recurrence relation if and only if When both sides of this equation are divided by (when ) and the right-hand side is subtracted from the left, we obtain the equation Consequently, the sequence with where is a solution if and only if is a solution of this last equation. We call this the characteristic equation of the recurrence relation. The solutions of this equation are called the characteristic roots of the recurrence relation.

The other key observation is that a linear combination of two solutions of a linear homogeneous recurrence relation is also a solution. To see this, suppose that and are both solutions of . Then and Now suppose that and are real numbers. Then This means that is also a solution of the same linear homogeneous recurrence relation.

We will now state the general result about the solution of linear homogeneous recurrence relations with constant coefficients, where the degree may be greater than two, under the assumption that the characteristic equation has distinct roots.

• Theorem: The General Case Let be real numbers. Suppose that the characteristic equation has distinct roots . Then a sequence is a solution of the recurrence relation if and only if for where are constants.

We now state the most general result about linear homogeneous recurrence relations with constant coefficients, allowing the characteristic equation to have multiple roots.

The key point is that for each root of the characteristic equation, the general solution has a summand of the form where is a polynomial of degree with the multiplicity of this root.

• Theorem: The General Case Let be real numbers. Suppose that the characteristic equation has distinct roots with multiplicities respectively, so that for and . Then a sequence is a solution of the recurrence relation if and only if for where are constants for and .

Linear Nonhomogeneous RR with Constant Coefficients

Let’s look at an example of linear nonhomogeneous recurrence relation with constant coefficients. For example, is an example of a linear nonhomogeneous recurrence relation with constant coefficients, that is, a recurrence relation of the form where are real numbers and is a function not identically zero depending only on . The recurrence relation is called the associated homogeneous recurrence relation. It plays an important role in the solution of the nonhomogeneous recurrence relation.

• Theorem: If is a particular solution of the nonhomogeneous linear recurrence relation with constant coefficients then every solution is of the form , where is a solution of the associated homogeneous recurrence relation We see that the key to solving nonhomogeneous recurrence relations with constant coefficients is finding a particular solution. Then every solution is a sum of this solution and a solution of the associated homogeneous recurrence relation. Although there is no general method for finding such a solution that works for every function there are techniques that work for certain types of functions such as polynomials and powers of constants.

• Theorem: Suppose that satisfies the linear nonhomogeneous recurrence relation where are real numbers, and where and are real numbers. When is not a root of the characteristic equation of the associated linear homogeneous recurrence relation, there is a particular solution of the form When is a root of this characteristic equation and its multiplicity is there is a particular solution of the form

Generating Functions

Generating functions are used to represent sequences efficiently by coding the terms of a sequence as coefficients of powers of a variable in a formal power series. Generating functions can be used to solve many types of counting problems, such as the number of ways to select or distribute objects of different kinds, subject to a variety of constraints, and the number of ways to make change for a rupee using coins of different denominations.

Generating functions can be used to solve recurrence relations by translating a recurrence relation for the terms of a sequence into an equation involving a generating function. This equation can then be solved to find a closed form for the generating function. From this closed form, the coefficients of the power series for the generating function can be found, solving the original recurrence relation.

Generating functions can also be used to prove combinatorial identities by taking advantage of relatively simple relationships between functions that can be translated into identities involving the terms of sequences.

• Theorem: The generating function for the sequence of real numbers is the infinite series

When generating functions are used to solve counting problems, they are usually considered to be formal power series. We will now state some widely important facts about infinite series used when working with generating functions.

• Theorem: Let and . Then

Theorem above is valid only for power series that converge in an interval. However, the theory of generating functions is not limited to such series. In the case of series that do not converge, the statements in Theorem above can be taken as definitions of addition and multiplication of generating functions.

To use generating functions to solve many important problems, we will need to apply the binomial theorem for exponents that are not positive integers. Before we state an extended version of the binomial theorem, we need to define extended binomial coefficients.

• Definition: Let be a real number and a nonnegative integer. Then the extended binomial coefficient is defined by

• Theorem: Let be a real number with and let be a real number. Then

Here is the table for useful generating functions:

Inclusion-Exclusion

How many elements are in the union of two finite sets? Previously we showed that the number of elements in the union of the two sets and is the sum of the numbers of elements in the sets minus the number of elements in their intersection. That is,

• Theorem: The Principle of Inclusion-Exclusion Let be finite sets. Then

Applications of Inclusion–Exclusion

Many counting problems can be solved using the principle of inclusion–exclusion. For instance, we can use this principle to find the number of primes less than a positive integer.

An Alternative Form: There is an alternative form of the principle of inclusion–exclusion that is useful in counting problems. In particular, this form can be used to solve problems that ask for the number of elements in a set that have none of properties .

Let be the subset containing the elements that have property . The number of elements with all the properties will be denoted by ). Writing these quantities in terms of sets, we have If the number of elements with none of the properties is denoted by following, and the number of elements in the set is denoted by it follows that From the inclusion–exclusion principle, we see that The next general result that tells us how many onto functions there are from a set with elements to one with elements.

• Theorem: Let and be positive integers with . Then, there are onto functions from a set with elements to a set with elements.

An onto function from a set with elements to a set with elements corresponds to a way to distribute the elements in the domain to indistinguishable boxes so that no box is empty, and then to associate each of the elements of the codomain to a box. This means that the number of onto functions from a set with elements to a set with elements is the number of ways to distribute distinguishable objects to indistinguishable boxes so that no box is empty multiplied by the number of permutations of a set with elements.

Consequently, the number of onto functions from a set with elements to a set with elements equals where is a Stirling number of the second kind.

A derangement is a permutation of objects that leaves no object in its original position. To solve the problem of similar kind we will need to determine the number of derangements of a set of objects.

• Theorem: The number of derangements of a set with elements is