The Art and Craft of Problem Solving

140 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS

Now it is clear that the weights 1,3,3^2 , ... , 3r can be used to weigh any integral

value from 1 to (Y - 1)/2 , in exactly one way. As r � 00, we get the limiting case, a

beautiful identity of generating functions:

Our final example is from the theory of partitions of integers, a subject first inves­

tigated by Euler. Given a positive integer n, a partition of n is a representation of n

as a sum of positive integers. The order of the summands does not matter, so they are

conventionally placed in increasing order. For example, 1 + 1 + 3 and 1 + 1 + 1 + 2 are

two different partitions of 5.

Example 4.3.7 Show that for each positive integer n, the number of partitions of n into

unequal parts is equal to the number of partitions of n into odd parts. For example, if

n = 6, there are four partitions into unequal parts, namely

1 +5, 1 +2+3, 2+4, (^6).
And there are also four partitions into odd parts,
1+1+1+1+1+1, 1+ 1 +1+3, 1+5, 3+3.
Solution: Let Un and Vn denote the number of partitions of n into unequal parts
and odd parts, respectively. It takes practice thinking in a generatingfunctionological
way, but by now you should have no trouble verifying (even if you had trouble coming
up with it) that
U(x) : = (1 +x)(1 +�)(1 +x^3 )(1 +x^4 )(1 +x» ...
is the generating function for (un). For example, the x 6 term in U(x) is equal to
x.x^5 +x.� ·x^3 +� ·x^4 +x^6 = 4x^6.
Notice that it is impossible to get a term like �. �; i.e., the generating function pre­
vents repeated parts in the partition.
If you are comfortable with U (x) (please do ponder it until it becomes "obvious"
to you that it is the correct generating function), you should try to construct V(x), the
generating function for (vn). The parts can be duplicated, but they all must be odd. For
example, if we wanted to include the possibility of zero, one, or two 3s in a partition,
the factor (1 +� +x (^6) ) would do the trick, since x 6 = x^2 -^3 plays the role of "two 3s."
Following this reasoning, we define the generating function
V (x) := (1 +x+x^2 +x^3 + .. ·)(1 +x^3 +x^6 +x 9 + ... )(1 +x> +xlO +x^15 + ... ) ....
Now, all that "remains" to be done is show that U (x) = V (x). The geometric series
tool provides an immediate simplification, yielding

V(x)= (- -- -- -- ...

1

)(

1

)(

1

)(

1

I- x 1 -x^3 l-x^5 1 -x 7 ).