Solving Combinatorial Problems Recursively

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

Example

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\), \(r(2)=4\), \(r(3)=7\) and \(r(4)=11\). To determine \(r(n)\) for all positive integers, it is enough to note that \(r(1)=2\), and when \(n>1\), \(r(n)=n+r(n-1)\). This formula follows from the observation that if we label the lines as \(L_1\), \(L_2, \dots, L_n\), 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 , where the line containing the three dots is \(L_4\). The other lines divide it into four segments, which then divide larger regions to create regions \(1\) and \(5\), \(2\) and \(6\), \(7\) and \(8\), and \(4\) and \(9\).

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

Example

A \(2\times n\) checkerboard will be tiled with rectangles of size \(2\times1\) and \(1\times2\). Find a recursive formula for the number \(t(n)\) of tilings. Clearly, \(t(1)=1\) and \(t(2)=2\). When \(n>2\), 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)\). In particular, \(t(3)=1+2=3\), \(t(4)=2+3=5\) and \(t(5)= 3+5=8\).

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

Example

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

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\), so there are \(g(n-1)\) such strings. The same applies for good strings ending in \(2\). For good strings ending in \(0\), 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\). There are \(g(n-1)\) good strings of length\(n-1\) and of these, exactly \(g(n-2)\) end in a\(2\). Therefore there are \(g(n-1)-g(n-2)\) good strings of length\(n\) that end in a\(0\). Hence the total number of good strings of length\(n\) satisfies the recursive formula \(g(n) = 3g(n-1) - g(n-2)\). Thus \(g(3) = 3\cdot8 -3= 21\) and \(g(4)= 3\cdot21-8= 55\).

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

Counting recursively

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

Example

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\), \(r(2)=4\), \(r(3)=7\) and \(r(4)=11\). To determine \(r(n)\) for all positive integers, it is enough to note that \(r(1)=2\), and when \(n>1\), \(r(n)=n+r(n-1)\). This formula follows from the observation that if we label the lines as \(L_1\), \(L_2, \dots, L_n\), 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 , where the line containing the three dots is \(L_4\). The other lines divide it into four segments, which then divide larger regions to create regions \(1\) and \(5\), \(2\) and \(6\), \(7\) and \(8\), and \(4\) and \(9\).

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

Example

A \(2\times n\) checkerboard will be tiled with rectangles of size \(2\times1\) and \(1\times2\). Find a recursive formula for the number \(t(n)\) of tilings. Clearly, \(t(1)=1\) and \(t(2)=2\). When \(n>2\), 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)\). In particular, \(t(3)=1+2=3\), \(t(4)=2+3=5\) and \(t(5)= 3+5=8\).

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

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

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.

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: Division Theorem

Let \(m\) and \(n\) be positive integers. Then there exist unique integers \(q\) and \(r\) so that \[\begin{aligned}\end{aligned}\] 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\), but there do not exist integers \(q\) and \(r\) with \(m=qn+r\) and \(0\le r\lt n\).

First, we note that \(n\neq 1\), for if \(n=1\), then we could take \(q=m\) and \(r=0\). Also, we cannot have \(m=1\), for if \(m=1\), then we can take \(q=0\) and \(r=1\). Now the statement holds for the pair \(m-1\), \(n\) so there are integers \(q\) and \(r\) so that \[\begin{aligned}\end{aligned}\] Since \(r\lt n\), we know that \(r+1\le n\). If \(r+1\lt n\), then \[\begin{aligned}\end{aligned}\] On the other hand, if \(r+1=n\), then \[\begin{aligned}\end{aligned}\] 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\). (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\). The greatest common divisor of \(m\) and \(n\), written \(\gcd(m,n)\), is the largest of all the common divisors of \(m\) and \(n\).

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

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\). We use the familiar notation m%n to denote the remainder \(r\) in the expression \(m=q\cdot n+r\), with \(0\le r \lt n\).

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.

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{aligned}\end{aligned}\] 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}\). How do we merge these two sequences into a single increasing sequence of length \(s+t\). 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\), 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\). 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\). Then let \(u_i=a_i\) for \(i=1,2,\dots,s\) and \(v_j=a_{s+j}\), for \(j=1,2,\dots,t\). Sort the two subsequences and then merge them. For a concrete example, given the sequence \((2,8,5,9,3,7,4,1,6)\), we split into \((2,8,5,9,3)\) and \((7,4,1,6)\). These subsequences are sorted (by a recursive call) into \((2,3,5,8,9)\) and \((1,4,6,7)\), 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\), since it clearly takes \(2n\) steps to merge two sorted sequences of length \(n\). This leads to the bound \(S(n) \lt C n\log n\) for some positive constant \(C\), and in computer science courses, you will learn (here it is an exercise) that this is optimal.

Symbols used here

\log_b x,\ \ln x

logarithm, natural log
The exponent b must be raised to for x; ln uses base e.

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

i

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

n!

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Solving Combinatorial Problems Recursively