Recursion 175
number, we need to consider the number of possibilities for the remaining partition.
The relationship can be expressed in this table:
Total First Number Remaining Value to Partition
n 1 n − 1
n 2 n − 2
n 3 n − 3
.
.
.
n n − 2 2
n n − 1 1
n n 0
These are all the possible cases and they are exclusive. If the first number is 1, then
the remaining value to be partitioned is n − 1. How many ways can n − 1 be partitioned?
By definition, it is f (n − 1). Continuing with this logic, if the first number is 2, then the
remaining value is n − 2, and by definition there are f(n − 2) ways to partition it. Using
recursion, we can assume that we have the answers to smaller versions of the problems.
This works because the smaller versions are expressed in terms of yet smaller versions, and
eventually we get to the trivial cases, i.e., f (1) = 1, and f(2) = 2.
The value of f (n) is therefore the sum of all the different cases when the first number is
1, 2, 3, . . . , n − 1, or n. Now, we can express f (n) as
f(n) =
1 if n is 1
f(n − 1) + f(n − 2) + . . . f(1) + 1 = 1 +
n−1
P
i=1
f(i) if n > 1
(12.8)
There is also a convenient closed form solution to f (n):
f(n) = f (n − 1) +f (n − 2) + f (n − 3) + ... + 1
− f(n − 1) = +f(n − 2) + f(n − 3) + ... + 1
f(n) − f (n − 1) = f (n − 1)
f(n) = 2f (n − 1)
f(n) = 4f (n − 2)
f(n) = 8f (n − 3)
f(n) = 16f (n − 4)
.
.
.
f(n) = 2
n−1
f(1)
f(n) = 2
n−1
(12.9)
Therefore there are 2
n−1
ways to partition the integer n.
12.4.1 Count the Number of “1”s
The partition problem has many variations. In this variation we count how many “1”s
are used for partitioning n. Suppose g(n) is the answer. First observe that g(1) = 1 and
g(2) = 2. The more complicated cases can be related to the simpler cases with the following
logic. Observe that there are 2
n−2
partitions of n that begin with the digit “1”. There may
be “1”s in the partitions of the remaining value, n − 1. Thus, when the first number is
“1”, we use 2
n−2
+ g(n − 1) “1”s. Notice again how we just assume we have the answer for
176 Intermediate C Programming
FIGURE 12.9: Count the occurrences of “1” when partitioning n.
smaller versions of the same function. We do not need to worry about the specific value of
g(n − 1), we just use it, confident that g(n − 1) will be expanded to g(n − 2), etc., until we
reach the trivial cases g(1) and g(2).
Continuing with this logic, when the first number is “2”, “1” is not used for the first
number but “1” may be used for partitioning the remaining value of n − 2. By definition,
“1” is used g(n − 2) times when partitioning n − 2.
Putting this all together, we calculate g(n) to be:
g(n) =
1 when n is 1
2
n−2
+ g(n − 1) + g(n − 2) + . . . g(1) = 2
n−2
+
n−1
P
i=1
g(i) when n > 1
(12.10)
To obtain the closed form, first find the relationship between g(n) and g(n − 1):
g(n) = 2
n−2
+ g(n − 1) +g(n − 2) + g(n − 3) + ... + g(1)
− g(n − 1) = 2
n−3
+g(n − 2) + g(n − 3) + ... + g(1)
g(n) − g(n − 1) = 2
n−3
+ g(n − 1)
g(n) = 2
n−3
+ 2g(n − 1)
(12.11)
This relationship can be expanded for g(n − 2), g(n − 3), ..., g(1).
g(n) = 2
n−3
+ 2g(n − 1)
g(n − 1) = 2
n−4
+ 2g(n − 2)
g(n − 2) = 2
n−5
+ 2g(n − 3)
.
.
.
g(n − k) = 2
n−k−3
+ 2g(n − k − 1)
.
.
.
g(3) = 2
0
+ 2g(2) when k = n − 3
(12.12)
In (12.12), the coefficient for g(n−1) on the right side is two. In order to cancel g(n −1),
the coefficient on the left size has to increase accordingly as shown below:
Recursion 177
g(n) = 2
n−3
+ 2g(n − 1)
2g(n − 1) = 2
n−3
+ 4g(n − 2)
4g(n − 2) = 2
n−3
+ 8g(n − 3)
.
.
.
2
k
g(n − k) = 2
n−3
+ 2
k+1
g(n − k − 1)
.
.
.
+ 2
n−3
g(3) = 2
n−3
+ 2
n−2
g(2)
g(n) +
n−1
P
i=3
2
n−i
g(i) = (n − 2)2
n−3
+ 2
n−2
g(2) +
n−1
P
i=3
2
n−i
g(i)
g(n) = (n − 2)2
n−3
+ 2
n−2
g(2)
g(n) = (n − 2)2
n−3
+ 2
n−1
g(n) = (n + 2)2
n−3
(12.13)
This table shows that the value of g(n) for 1 ≤ n ≤ 10. If a formula does not match
these cases, the formula is definitely wrong. However, matching these cases does not mean
that the formula is correct. It is necessary to have a systematic way to find the formula. It
is generally a bad idea to find a formula to match these finite values.
n 1 2 3 4 5 6 7 8 9
g(n) 1 2 5 12 28 64 144 320 704
12.4.2 Odd Numbers Only
In this variation of the partition problem we want to find how many ways n can be
partitioned without using any even number. It may be helpful to review how Equation (12.8)
is derived. What does f(n − 1) mean in this equation? It means the number of partitions
using “1” as the first number. Similarly, what does f (n −2) mean in this equation? It means
the number of partitions using “2” as the first number. To restrict the partitions to odd
numbers only, all partitions using even numbers must be discarded. Thus, f (n−2), f(n−4),
f(n − 6), etc., must be excluded. Suppose h(n) is the number of partitions for n using odd
numbers only.
h(n) = h(n − 1) + h(n − 3) + h(n − 5)... when n > 1 (12.14)
The last few terms will be different depending on whether n itself is odd or even. If n is
odd, n − 1 is even so h(1) is excluded. Also n − 1, n − 3, ..., are all even numbers. The
complete equation is shown below:
h(n) =
(
1 when n is 1
h(n − 1) + h(n − 3) + h(n − 5)... + h(2) + 1 when n > 1 and n is odd
(12.15)
If n is even, n − 1 is odd so h(1) is included. Also n − 1, n − 3, ..., are all odd numbers.
Therefore the complete equation is shown below:
178 Intermediate C Programming
h(n) =
1 when n is 1
h(n − 1) + h(n − 3) + h(n − 5)... + h(2) + 1 when n > 1 and n is odd
h(n − 1) + h(n − 3) + h(n − 5)... + h(1) when n is even
(12.16)
12.4.3 Increasing Values
How many ways can the positive integer n be partitioned using increasing values or the
number n itself? Suppose n is partitioned into the sum of k numbers:
n = a
1
+ a
2
+ a
3
+ ... + a
k
(12.17)
The following conditions must be true:
• a
i
(1 ≤ i ≤ k) are positive integers
• a
i
< a
i+1
(1 ≤ i < k)
Consider the first few cases of n:
• When n is 1, 1 is a valid partition.
• When n is 2, 2 is a valid partition but 1 + 1 is invalid.
• When n is 3, 1 + 2 and 3 are two valid partitions; 1 + 1 + 1, and 2 + 1 are invalid
partitions.
• When n is 4, 1 + 3 is a valid partition; 2 + 2 and 3 + 1 are invalid partitions.
• When n is 5, 1 + 4, 2 + 3 are valid partitions; 2 + 2 + 1, 3 + 2, 4 +1 are invalid
partitions.
To solve this problem, two arguments are needed for the equation. We define p(n, m)
to be the number of ways to partition n where m is the smallest number used. When
partitioning n, note the following:
• If 1 is used as the first number, then 2 is the smallest number that can be used when
partitioning n − 1. There are p(n − 1, 2) ways to partition n − 1 using 2 as the smallest
number.
• If 2 is used as the first number, then 3 is the smallest number that can be used to
partition n − 2. There are p(n − 2, 3) ways to partition n − 2 using 3 as the smallest
number.
• If 3 is used as the first number, then 4 is the smallest number that can be used to
partition n − 3. There are p(n − 3, 4) ways to partition n − 3 using 4 as the smallest
number.
Based on this reasoning,
p(n, 1) = p(n − 1, 2) + p(n − 2, 3) + ... + p(n − k, k + 1) + ... + p(1, n) + 1
= 1 +
n−1
P
i=1
p(n − i, i + 1)
(12.18)
By inspection we can tell that p(n, n) = 1. This means that there is one and only one
way to partition n using n as the smallest number. Also, p(n, m) = 0 if n < m because it
is impossible to partition an integer using a larger integer. This problem is different from
the previous ones because the recursive equations require two arguments. The fundamental
recursive reasoning is the same.
Recursion 179
12.4.4 Alternating Odd and Even Numbers
In this variation of the problem we want to find partitions that alternate between odd
and even numbers. If an odd number is used, then the next must be an even number. If an
even number is used, then the next must be an odd number. If only one number is used
(i.e., the number to be partitioned), then this restriction does not apply and it is always a
valid partition. This restriction allows only the following partitions for 1 to 7:
1 = 1 2 = 2 3 = 1 + 2 4 = 1 + 2 + 1
= 2 + 1 = 4
= 3
5 = 1 + 4 6 = 1 + 2 + 1 + 2 7 = 1 + 2 + 1 + 2 + 1
= 2 + 1 + 2 = 1 + 2 + 3 = 1 + 6
= 2 + 3 = 1 + 4 + 1 = 2 + 1 + 4
= 3 + 2 = 2 + 1 + 2 + 1 = 2 + 3 + 2
= 4 + 1 = 3 + 2 + 1 = 2 + 5
= 5 = 6 = 3 + 4
= 4 + 1 + 2
= 4 + 3
= 5 + 2
= 6 + 1
= 7
The following table shows the solutions for n between 1 and 10.
n 1 2 3 4 5 6 7 8 9 10
number of partitions 1 1 3 2 6 6 11 16 22 37
This problem using alternating odd and even numbers can be solved by defining two
functions as follows:
• s(n) is the number of ways to partition n using an odd number as the first number.
• t(n) is the number of ways to partition n using an even number as the first number.
By observation we can create the following table:
n 1 2 3 4 5
s(n) 1 0 2 1 3
t(n) 0 1 1 1 3
sum 1 1 3 2 6
To calculate s(n), the first number can be 1, 3, 5, ... and the second number must be an
even number. For example, when 1 is used for the first number, then the remaining n − 1
must start with an even number. By definition, there are t(n − 1) ways to partition n − 1
starting with an even number. When 3 is used for the first number, then there are t(n − 3)
ways to partition n − 3 starting with an even number. Based on this reasoning, s(n) is
defined as:
s(n) = t(n − 1) + t(n − 3) + t(n − 5)... (12.19)
By definition, s(n) must not start with an even number and t(n − 2), t(n − 4), ... must not
be included.
It is necessary to distinguish whether n is odd or even while writing down the last few
terms in this equation. If n is an even number then:
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.