Counting with polynomials
Tonight's idea
You have 1-cent coins, at most two of them, and a 3-cent coin, at most one. Write a polynomial for each coin whose exponents are the amounts it can contribute: \(1 + x + x^2\) for the pennies (0, 1 or 2 cents) and \(1 + x^3\) for the 3-cent coin. Multiply:
\((1 + x + x^2)(1 + x^3) = 1 + x + x^2 + x^3 + x^4 + x^5.\)
When you multiply out, each term of the product picks one term from each bracket, and the exponents add. So \(x^n\) appears once for every way of choosing coins totalling \(n\) cents: the coefficient of \(x^n\) counts the ways. Every amount from 0 to 5 can be made in exactly one way.
The polynomial is a generating function for the sequence of counts. The letter \(x\) is just a place to hang exponents; nothing is plugged in. The payoff is that algebra on the function does the counting. Unlimited pennies give \(1 + x + x^2 + \cdots = \frac{1}{1 - x}\), the infinite geometric series from grade 10. Unlimited 1s and 5s give \(\frac{1}{(1 - x)(1 - x^5)}\); expanding it reads off every count. The binomial theorem is the same idea: \((1 + x)^n\) takes each of \(n\) objects or not.
Watch one: Fibonacci in one fraction
Let \(F(x) = F_0 + F_1 x + F_2 x^2 + \cdots = x + x^2 + 2x^3 + 3x^4 + 5x^5 + \cdots\), with \(F_0 = 0\), \(F_1 = 1\). The rule \(F_n = F_{n-1} + F_{n-2}\) for \(n \ge 2\) says that the coefficient of \(x^n\) in \(F(x)\) equals the coefficient of \(x^n\) in \(xF(x) + x^2F(x)\). The two agree from \(x^2\) onward and differ only in the \(x\) term, so \(F(x) - xF(x) - x^2F(x) = x\):
\(F(x) = \dfrac{x}{1 - x - x^2}.\)
Check by multiplying back: \((1 - x - x^2)(x + x^2 + 2x^3 + 3x^4 + 5x^5 + \cdots) = x\), every other term cancelling in pairs. The whole infinite sequence sits inside one fraction. The next sheet gets a formula for \(F_n\) from the same recurrence another way.
Your turn
- Expand \((1 + x)(1 + x^2)(1 + x^4)\). What does the result say about writing the numbers 0 to 7 as sums of distinct powers of 2?
- Two dice: \((x + x^2 + \cdots + x^6)^2\). (a) Find the coefficients of \(x^7\), \(x^9\) and \(x^{10}\), and the probability of each total. (b) Put \(x = 1\). What does the number you get count?
- Unlimited 2-cent and 3-cent stamps: \(\frac{1}{(1 - x^2)(1 - x^3)}\). Expand \((1 + x^2 + x^4 + x^6 + x^8)(1 + x^3 + x^6)\) and list the coefficients of \(x^0, \dots, x^8\). Which amounts cannot be made? In how many ways can 6 be made?
- Unlimited 1s and 2s: \(C(x) = \sum c_n x^n = \frac{1}{(1 - x)(1 - x^2)}\). (a) Find \(c_0, \dots, c_6\) by expanding. (b) Multiply \(C(x)\) by \(1 - x^2\) and simplify. Compare coefficients of \(x^n\) on both sides to prove \(c_n = c_{n-2} + 1\) for \(n \ge 2\). (c) Give a formula for \(c_n\).
Stretch: 1/89
A generating function can be evaluated when its series converges. Put \(x = \tfrac{1}{10}\) into \(F(x) = \frac{x}{1 - x - x^2}\) and simplify. Then compute \(1/89\) to ten decimal places and explain what you see. Why does the pattern eventually blur?
Answers
- \(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7\). Every number from 0 to 7 is a sum of distinct powers of 2 in exactly one way: binary notation exists and is unique.
- (a) Coefficients 6, 4, 3, so \(P(7) = \tfrac{6}{36}\), \(P(9) = \tfrac{4}{36}\), \(P(10) = \tfrac{3}{36}\). (b) \(6^2 = 36\): setting \(x = 1\) adds up all the coefficients, the total number of ordered outcomes.
- Coefficients of \(x^0, \dots, x^8\): 1, 0, 1, 1, 1, 1, 2, 1, 2. Only 1 cent cannot be made. Six can be made in two ways: \(2 + 2 + 2\) and \(3 + 3\).
- (a) \(1, 1, 2, 2, 3, 3, 4\). (b) \((1 - x^2)C(x) = \frac{1}{1 - x} = 1 + x + x^2 + \cdots\). The coefficient of \(x^n\) on the left is \(c_n - c_{n-2}\); on the right it is 1. So \(c_n = c_{n-2} + 1\). (c) \(c_n = \lfloor n/2 \rfloor + 1\): choose 0, 1, …, \(\lfloor n/2 \rfloor\) two-cent coins and fill the rest with pennies.
Stretch. \(F(\tfrac{1}{10}) = \dfrac{1/10}{1 - 1/10 - 1/100} = \dfrac{10}{89}\), so \(\dfrac{1}{89} = \displaystyle\sum_{n \ge 1} \frac{F_n}{10^{\,n+1}} = 0.01 + 0.001 + 0.0002 + 0.00003 + 0.000005 + 0.0000008 + \cdots\), and indeed \(1/89 = 0.0112359550\ldots\) The digits 1, 1, 2, 3, 5, 8 are visible; from \(F_7 = 13\) onward the terms have two or more digits and carry into each other, so the pattern blurs. The series converges because \(F_n\) grows like \(\varphi^n \approx 1.618^n\), slower than \(10^n\); it would fail for \(x \ge 1/\varphi \approx 0.618\).