136 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS
Partitions
Consider the following polynomial product:P(x) := (2 + 3x+ 1)(^2 + 2x + 1) = x^4 + 5x^3 + 8^2 +5x+ 1.
How did we compute the coefficient of:xk in P(x)? For example, the X^2 term is the sum
- 1 + 3x. 2x + 1 · (^2) = 8x^2 ,
so the coefficient is 8. In general, to find the:xk term of P(x), we look at all pairings of
terms, where one term comes from the first factor and the other comes from the secondfactor and the exponents add up to k. We multiply the pairs, and then add them up, and
that is our answer.Now let us rewrite P(x) as
(x^2 +x+x+x+ 1)(^2 +x+x+ 1). (3)
The product will be unchanged, of course, so for example, the X^2 term is still 8X^2. This
corresponds to the sum(^2) ·1 +x·x+x · x+x·x+x·x+x·x+x·x+ 1· (^2).
All that really matters here are the exponents; we can list the pairings of exponents by
the sums
2 +0, 1+1, 1 + 1 , 1 + 1 , 1 + 1 , 1+1, 1+1, 0+2,
and all we need to do is count the number of sums (there are eight). Here's anotherway to think of it. Imagine that the first factor of (3) is colored red and the second
factor is colored blue. We can reformulate our calculation of the X^2 coefficient in the
following way:
Assume that you have one red 2, three red 1 s and one red 0; and one
blue 2, two blue 1 s and one blue O. Then there are eight different ways
that you can add a red number and a blue number to get a sum of 2.
At this point, you are probably saying, "So what? ," so it is time for an example.
Example 4.3.5 How many distinct ordered pairs (a, b) of non-negative integers satisfy2a+5b = 100?
Solution: Look at the general case: Let Un be the number of nonnegative ordered
pairs that solve 2 a + 5b = n. Thus Uo = 1 , UI = 0, U 2 = 1 , etc. We need to find UIOO.
Now defineA(x) = 1 +x^2 +x^4 +x^6 +x^8 +" ',
B(x) = 1 +x^5 +xlO +x^15 +^20 +" ',
and consider the productA(x)B(x) = ( 1 +^2 +x(^4) + ..
·)(1 +� +xlO + ... )
= 1 +x^2 +x^4 +x^5 +x^6 +x^7 +x^8 +x^9 +2x^1 O + ....