Intermediate C Programming

180 Intermediate C Programming

• n − 3 is an odd number. This means that there are t(n − (n − 3)) = t(3) ways to

partition n with n − 3 as the ﬁrst number. For example, if n = 10, there are t(3) ways

to partition 10 with 7 as the ﬁrst number. Note that t(3) = 1, because the only valid

partition of 3 that starts with an even number is: 3 = 2 + 1.

• n − 2 is an even number. We skip this case because s(n) is only concerned with the

number of ways to partition n using an odd number as the ﬁrst number.

• n − 1 is an odd number, so t(n − (n − 1)) = t(1) is included in the calculation of s(n).

Note, however, that t(1) = 0.

• n is an even number. We skip this case because s(n) only concerns itself with partitions

that begin with odd numbers.

Hence, when n is an even number:

s(n) = t(n − 1) + t(n − 3) + t(n − 5)... + t(3) + t(1) (12.20)

Following this logic when n is an odd number:

• n − 3 is an even number and this case is discarded when computing s(n). For example,

if n = 11, then n − 3 = 8, which is even. Since s(n) only concerns itself with partitions

that begin with an odd number, we skip t(3).

• n − 2 is an odd number leaving the remainder 2 to be partitioned. Thus we add t(2).

• n − 1 is an even number and this case is discarded when computing s(n).

• n is an odd number and it is a valid partition for s(n). This means we add 1 to the

end of the equation.

When n is an odd number, s(n) can be written as:

s(n) = t(n − 1) + t(n − 3) + t(n − 5)... + t(2) + 1 (12.21)

Combining these two halves together, we get:

s(n) =

(

t(n − 1) + t(n − 3) + t(n − 5)... + t(1) when n is even

t(n − 1) + t(n − 3) + t(n − 5)... + t(2) + 1 when n is odd

(12.22)

Using similar reasoning again, t(n) can be written as follows:

t(n) =

(

s(n − 2) + s(n − 4) + s(n − 6)... + s(4) + s(2) + 1 when n is even

s(n − 2) + s(n − 4) + s(n − 6)... + s(3) + s(1) when n is odd

(12.23)

Since a partition may start with an odd number or an even number, f(n) = s(n) + t(n)

and it is the answer to the question. This is the number of ways to partition n using alter-

nating odd and even numbers. Section 12.4.2 explains how to ﬁnd the number of partitions

using odd numbers only. The answer is expressed as h(n). A similar procedure can be used

to ﬁnd the number of partitions using even numbers only. Let’s call it u(n). Of course, u(n)

is zero if n is odd.

Is h(n) + u(n) the same as s(n) + t(n)? Why? I leave this question for you to answer. If

the answer is yes, prove it. If the answer is no, explain the reason.

12.4.5 Generalizing the Integer Partition Problem

This problem has many variations, for example,

• How many “2”s are used?

• How many “3”s are used?, etc.

Recursion 181

• How many “+” symbols are used?

• How many numbers are used, and what is the general rule?

– When n is 1, one number is used.

– When n is 2, three numbers are used.

– When n is 3, eight numbers are used.

– When n is 4, twenty numbers are used.

12.4.6 How Not to Solve the Integer Partition Problem

Sometimes people try to solve these types of problems in the following way:

1. Manually count the answers for the ﬁrst several values of n.

2. Observe the relationships and write a formula that satisﬁes these relationships.

3. Claim this formula is the answer.

This approach is logically ﬂawed. For any ﬁnite number of pairs of (x

, y

), (x

, y

), (x

, y

... , (x

, y

), there is always a polynomial y = a

+ a

k−1

+ ... + a

x + a

that passes

through these points. That does not mean this polynomial is the correct formula. In fact,

the previous examples show that the answers are not polynomials.

There is another explanation for why “conclusion by observation” is logically ﬂawed. Do

you have a favorite television program that is broadcast daily? By observation, this program

is on air every day. Can you claim that this program will be on air forever? Of course not.

The program may stop after a few seasons or a few years. Observation of ﬁnite instances

is not a valid way to derive a general rule. Even after a thousand observations, you cannot

guarantee that it is still true next time.

The equations in (12.8), (12.9), (12.10), and (12.12) are not derived from observation of

ﬁnite cases. The equations are correct for any positive integer n. In some cases n must be

greater than some speciﬁc value, for example, n > 1 in (12.10). The equations are general

and the derivations from these equations are logically sound. When you solve this type of

problem, please remember that observation is insuﬃcient.

Recursive formulas are actually reasonably straightforward with some practice. The key

is realizing that without using recursion, the problem may be really diﬃcult. The simplicity

of recursion is that you can assume that you already have the answer to smaller cases.

Therefore if you can write f (n) in terms of f (smaller than n), and if you can write trivial

cases like f(0) and f(1), then that is the entire solution.

This page intentionally left blankThis page intentionally left blank

Previous Chapter

12. Recursion (3/4)

Next Chapter

13. Recursive C Functions (1/4)

Table of Contents for Intermediate C Programming

Table of Contents for
Intermediate C Programming