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 first number. For example, if n = 10, there are t(3) ways
to partition 10 with 7 as the first 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 first 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 find the number of partitions
using odd numbers only. The answer is expressed as h(n). A similar procedure can be used
to find 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 first several values of n.
2. Observe the relationships and write a formula that satisfies these relationships.
3. Claim this formula is the answer.
This approach is logically flawed. For any finite number of pairs of (x
1
, y
1
), (x
2
, y
2
), (x
3
, y
3
),
... , (x
k
, y
k
), there is always a polynomial y = a
k
x
k
+ a
k−1
x
k−1
+ ... + a
1
x + a
0
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 flawed. 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 finite 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
finite cases. The equations are correct for any positive integer n. In some cases n must be
greater than some specific 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 insufficient.
Recursive formulas are actually reasonably straightforward with some practice. The key
is realizing that without using recursion, the problem may be really difficult. 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
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.