AC Solving Combinatorial Problems Recursively

Section 3.5 Solving Combinatorial Problems Recursively

Subsection 3.5.1 Counting recursively

In this section, we present examples of combinatorial problems for which solutions can be computed recursively. In Chapter 9, we return to these problems and obtain even more compact solutions. Our first problem is one discussed in our introductory chapter.

Example 3.3.

A family of \(n\) lines is drawn in the plane with (1) each pair of lines crossing and (2) no three lines crossing in the same point. Let \(r(n)\) denote the number of regions into which the plane is partitioned by these lines. Evidently, \(r(1)=2\text{,}\) \(r(2)=4\text{,}\) \(r(3)=7\) and \(r(4)=11\text{.}\) To determine \(r(n)\) for all positive integers, it is enough to note that \(r(1)=2\text{,}\) and when \(n>1\text{,}\) \(r(n)=n+r(n-1)\text{.}\) This formula follows from the observation that if we label the lines as \(L_1\text{,}\) \(L_2, \dots, L_n\text{,}\) then the \(n-1\) points on line \(L_n\) where it crosses the other lines in the family divide \(L_n\) into \(n\) segments, two of which are infinite. Each of these segments is associated with a region determined by the first \(n-1\) lines that has now been subdivided into two, giving us \(n\) more regions than were determined by \(n-1\) lines. This situation is illustrated in Figure 3.4, where the line containing the three dots is \(L_4\text{.}\) The other lines divide it into four segments, which then divide larger regions to create regions \(1\) and \(5\text{,}\) \(2\) and \(6\text{,}\) \(7\) and \(8\text{,}\) and \(4\) and \(9\text{.}\)

Figure 3.4. Lines and regions in the plane

With the recursive formula, we thus have \(r(5)=5+11=16\text{,}\) \(r(6)=6+16=22\) and \(r(7)=7+22=29\text{.}\) Even by hand, it wouldn’t be all that much trouble to calculate \(r(100)\text{.}\) We could do it before lunch.

Example 3.5.

A \(2\times n\) checkerboard will be tiled with rectangles of size \(2\times1\) and \(1\times2\text{.}\) Find a recursive formula for the number \(t(n)\) of tilings. Clearly, \(t(1)=1\) and \(t(2)=2\text{.}\) When \(n>2\text{,}\) consider the rectangle that covers the square in the upper right corner. If it is vertical, then preceding it, we have a tiling of the first \(n-1\) columns. If it is horizontal, then so is the rectangle immediately underneath it, and proceeding them is a tiling of the first \(n-2\) columns. This shows that \(t(n)=t(n-1)+t(n-2)\text{.}\) In particular, \(t(3)=1+2=3\text{,}\) \(t(4)=2+3=5\) and \(t(5)= 3+5=8\text{.}\)

Again, if compelled, we could get \(t(100)\) by hand, and a computer algebra system could get \(t(1000)\text{.}\)

Example 3.6.

Call a ternary string good if it never contains a \(2\) followed immediately by a \(0\text{;}\) otherwise, call it bad. Let \(g(n)\) be the number of good strings of length \(n\text{.}\) Obviously \(g(1)=3\text{,}\) since all strings of length \(1\) are good. Also, \(g(2)=8\) since the only bad string of length \(2\) is \((2,0)\text{.}\) Now consider a value of \(n\) larger than \(2\text{.}\)

Partition the set of good strings of length \(n\) into three parts, according to the last character. Good strings ending in \(1\) can be preceded by any good string of length \(n-1\text{,}\) so there are \(g(n-1)\) such strings. The same applies for good strings ending in \(2\text{.}\) For good strings ending in \(0\text{,}\) however, we have to be more careful. We can precede the \(0\) by a good string of length \(n-1\) provided that the string does not end in \(2\text{.}\) There are \(g(n-1)\) good strings of length \(n-1\) and of these, exactly \(g(n-2)\) end in a \(2\text{.}\) Therefore there are \(g(n-1)-g(n-2)\) good strings of length \(n\) that end in a \(0\text{.}\) Hence the total number of good strings of length \(n\) satisfies the recursive formula \(g(n) = 3g(n-1) - g(n-2)\text{.}\) Thus \(g(3) = 3\cdot8 -3= 21\) and \(g(4)= 3\cdot21-8= 55\text{.}\)

Once more, \(g(100)\) is doable by hand, while even a modest computer can be coaxed into giving us \(g(5000)\text{.}\)

Reading Questions Reading Questions

1.

Suppose we are defining a function \(f(n)\) recursively, and we want to define it for all positive integers \(n\) (and that it doesn’t make sense to define it for \(n\leq 0\)). Suppose we figure out that the recursive relation for \(f\) is \(f(n) = 3f(n-3) + 2f(n-2)-f(n-1)\text{.}\) What is the smallest value of \(n\) for which it would make sense to use this recursive formula? For what values of \(n\) do you need to know the value of \(f(n)\) in order to make the recursive formula work? Be sure to write a sentence or two to explain your reasoning.

2.

Recall that a ternary string is a string in which the allowed symbols are \(0\text{,}\) \(1\text{,}\) and \(2\text{.}\) Call a ternary string “good” if it does not contain a \(1\) followed immediately by a \(2\text{.}\) Let \(g(n)\) be the number of good strings of length \(n\text{.}\) Find \(g(1)\) and \(g(2)\) and explain why for all \(n\geq 3\text{,}\) \(g(n)=3g(n-1) - g(n-2)\text{.}\)

Hint.

It may be helpful to think of \(3g(n-1) - g(n-2)\) as \(2g(n-1) + (g(n-1)- g(n-2))\text{.}\)

Subsection 3.5.2 Finding Greatest Common Divisors

There is more meat than you might think to the following elementary theorem, which seems to simply state a fact that you’ve known since second grade.

Theorem 3.7. Division Theorem.

Let \(m\) and \(n\) be positive integers. Then there exist unique integers \(q\) and \(r\) so that

\begin{equation*} m = q\cdot n+r\quad\text{and} \quad 0 \le r \lt n. \end{equation*}

We call \(q\) the quotient and \(r\) the remainder.

Proof.

We settle the claim for existence. The uniqueness part is just high-school algebra. If the theorem fails to hold, then let \(t\) be the least positive integer for which there are integers \(m\) and \(n\) with \(m+n=t\text{,}\) but there do not exist integers \(q\) and \(r\) with \(m=qn+r\) and \(0\le r\lt n\text{.}\)

First, we note that \(n\neq 1\text{,}\) for if \(n=1\text{,}\) then we could take \(q=m\) and \(r=0\text{.}\) Also, we cannot have \(m=1\text{,}\) for if \(m=1\text{,}\) then we can take \(q=0\) and \(r=1\text{.}\) Now the statement holds for the pair \(m-1\text{,}\) \(n\) so there are integers \(q\) and \(r\) so that

\begin{equation*} m-1 = q\cdot n+r\quad\text{and} \quad 0 \le r \lt n. \end{equation*}

Since \(r\lt n\text{,}\) we know that \(r+1\le n\text{.}\) If \(r+1\lt n\text{,}\) then

\begin{equation*} m = q\cdot n+(r+1)\quad\text{and} \quad 0 \le r+1 \lt n. \end{equation*}

On the other hand, if \(r+1=n\text{,}\) then

\begin{equation*} m = q\cdot n+(r+1)=nq+n=(q+1)n=(q+1)n+0. \end{equation*}

The contradiction completes the proof.

Recall that an integer \(n\) is a divisor of an integer \(m\) if there is an integer \(q\) such that \(m=qn\text{.}\) (We write \(n\mid m\) and read “\(n\) divides \(m\)”.) An integer \(d\) is a common divisor of integers \(m\) and \(n\) if \(d\) is a divisor of both \(m\) and \(n\text{.}\) The greatest common divisor of \(m\) and \(n\text{,}\) written \(\gcd(m,n)\text{,}\) is the largest of all the common divisors of \(m\) and \(n\text{.}\)

Here’s a particularly elegant application of the preceding basic theorem:

Theorem 3.8. Euclidean Algorithm.

Let \(m,n\) be positive integers with \(m\gt n\) and let \(q\) and \(r\) be the unique integers for which

\begin{equation*} m = q\cdot n+r\quad\text{and} \quad 0 \le r \lt n. \end{equation*}

If \(r>0\text{,}\) then \(\gcd(m,n)=\gcd(n,r)\text{.}\) If \(r=0\text{,}\) then \(n\) divides \(m\text{,}\) and \(\gcd(m,n) = n\text{.}\)

Proof.

Consider the expression \(m=q\cdot n+r\text{,}\) which is equivalent to \(m-q\cdot n = r\text{.}\) If a number \(d\) is a divisor of \(m\) and \(n\text{,}\) then \(d\) must also divide \(r\text{.}\) Similarly, if \(d\) is a divisor of \(n\) and \(r\text{,}\) then \(d\) must also divide \(m\text{.}\)

Here is a code snippet that computes the greatest common divisor of \(m\) and \(n\) when \(m\) and \(n\) are positive integers with \(m\ge n\text{.}\) We use the familiar notation m%n to denote the remainder \(r\) in the expression \(m=q\cdot n+r\text{,}\) with \(0\le r \lt n\text{.}\)

Feel free to change the values 12 and 5 above in the SageMath cell in the HTML version of the text to calculate the greatest common divisor of some other integers. Just remember that the code assumes \(m\geq n\) when you do so!

The disadvantage of this approach is the somewhat wasteful use of memory due to recursive function calls. It is not difficult to develop code for computing the greatest common divisor of \(m\) and \(n\) using only a loop, i.e., there are no recursive calls. With minimal extra work, such code can also be designed to solve the following diophantine equation problem:

Theorem 3.9.

Let \(m\text{,}\) \(n\text{,}\) and \(c\) be positive integers. Then there exist integers \(a\) and \(b\text{,}\) not necessarily non-negative, solving the linear diophantine equation \(am+bn=c\) if and only if \(c\) is a multiple of the greatest common divisor of \(m\) and \(n\text{.}\)

Let’s see how the Euclidean algorithm can be used to write \(\gcd(m,n)\) in the form \(am+bn\) with \(a,b\in\ints\) with the following example.

Example 3.10.

Find the greatest common divisor \(d\) of \(3920\) and \(252\) and find integers \(a\) and \(b\) such that \(d=3920a+252b\text{.}\)

Solution.

In solving the problem, we demonstrate how to perform the Euclidean algorithm so that we can find \(a\) and \(b\) by working backward. First, we note that

\begin{equation*} 3920 = 15\cdot 252 + 140. \end{equation*}

Now the Euclidean algorithm tells us that \(\gcd(3920,252)=\gcd(252,140)\text{,}\) so we write

\begin{equation*} 252 = 1\cdot 140 + 112. \end{equation*}

Continuing, we have \(140= 1\cdot 112 + 28\) and \(112 = 4\cdot 28+0\text{,}\) so \(d=28\text{.}\)

To find \(a\) and \(b\text{,}\) we now work backward through the equations we found earlier, “solving” them for the remainder term and then substituting. We begin with

\begin{equation*} 28 = 140-1\cdot 112. \end{equation*}

But we know that \(112=252-1\cdot 140\text{,}\) so

\begin{equation*} 28=140-1(252-1\cdot 140) = 2\cdot 140 - 1\cdot 252. \end{equation*}

Finally, \(140 = 3920-15\cdot 252\text{,}\) so now we have

\begin{equation*} 28= 2(3920-15\cdot 252) - 1\cdot 252 = 2\cdot 3920-31\cdot 252. \end{equation*}

Therefore \(a=2\) and \(b=-31\text{.}\)

Subsection 3.5.3 Sorting

One of the most common and most basic computing problems is sorting: Given a sequence \(a_1,a_2,\dots,a_n\) of \(n\) distinct integers, rearrange them so that they are in increasing order. We describe here an easy recursive strategy for accomplishing this task. This strategy is known as Merge Sort, and it is one of several optimal algorithms for sorting. Introductory computer science courses treat this topic in greater depth. In our course, we simply need some good strategy and merge sort works fine for our purposes.

To present merge sort, must first develop a strategy for solving a special case of the sorting problem. Suppose we have \(s+t\) distinct integers

\begin{equation*} \{u_0,u_1,\dots,u_{s-1},v_0,v_1,\dots,v_{t-1}\} \end{equation*}

arranged as two lists with \(u_0\lt u_1\lt \dots\lt u_{s-1}\) and \(v_0\lt v_1\lt \dots\lt v_{t-1}\text{.}\) How do we merge these two sequences into a single increasing sequence of length \(s+t\text{.}\) Imagine the two sequences placed on two horizontal lines, one immediately under the other. Then let \(u\) be the least integer in the first sequence and \(v\) the least integer in the second. At the moment, this implies that \(u=u_0\) and \(v=v_0\text{,}\) but integers will be deleted from the two sequences as the process is carried out. Regardless, the meaning of \(u\) and \(v\) will be preserved. Also, set \(i=0\text{.}\) Then take \(a_i\) as the minimum of \(u\) and \(v\) and delete \(a_i\) from the sequence in which it occurs. Then increase \(i\) by \(1\) and repeat. Here is a code snippet for accomplishing a merge operation, with \(u_p\) now written as u[p] and \(v_q\) now written as v[q].

Now that we have a good strategy for merging, it is easy to develop a recursive strategy for sorting. Given a sequence \(a_1,a_2,\dots,a_n\) of \(n\) distinct integers, we set \(s=\lceil n/2\rceil\) and \(t=\lfloor n/2\rfloor\text{.}\) Then let \(u_i=a_i\) for \(i=1,2,\dots,s\) and \(v_j=a_{s+j}\text{,}\) for \(j=1,2,\dots,t\text{.}\) Sort the two subsequences and then merge them. For a concrete example, given the sequence \((2,8,5,9,3,7,4,1,6)\text{,}\) we split into \((2,8,5,9,3)\) and \((7,4,1,6)\text{.}\) These subsequences are sorted (by a recursive call) into \((2,3,5,8,9)\) and \((1,4,6,7)\text{,}\) and then these two sorted sequences are merged.

For running time, if \(S(n)\) is the number of operations it takes to sort a sequence of \(n\) distinct integers, then \(S(2n)\le2 S(n) + 2n\text{,}\) since it clearly takes \(2n\) steps to merge two sorted sequences of length \(n\text{.}\) This leads to the bound \(S(n) \lt C n\log n\) for some positive constant \(C\text{,}\) and in computer science courses, you will learn (here it is an exercise) that this is optimal.

You have attempted of activities on this page.

Prev Top Next