Let a_n count the ordered ways to write n as a sum of 1s, 2s and 3s, so a_3 = 4. Give the generating function, the recurrence it encodes, and the value of a_10.

Let a_n count the ordered ways to write n as a sum of 1s, 2s and 3s, so a_3 = 4. Give the generating function, the recurrence it encodes, and the value of a_10.

Approach: Each summand contributes a geometric factor, so multiply the three part sizes into one rational function, then read the denominator as the recurrence and iterate from the base cases.

274. A composition into parts of size 1, 2 or 3 is a sequence of such parts, so the generating function is sum over k of (x + x^2 + x^3)^k = 1/(1 - x - x^2 - x^3), a rational function whose coefficient of x^n is a_n. Clearing the denominator gives (1 - x - x^2 - x^3) * A(x) = 1, whose coefficient comparison is the linear recurrence a_n = a_{n-1} + a_{n-2} + a_{n-3} with a_0 = 1, a_1 = 1, a_2 = 2. The recurrence is the direct combinatorial statement that the first part is 1, 2 or 3. Iterating gives 4, 7, 13, 24, 44, 81, 149, 274 for n from 3 to 10, so a_10 = 274. The growth rate is the real root of x^3 = x^2 + x + 1, about 1.8393, so a_n roughly triples every two steps.

Follow-up: How does the generating function change if no two consecutive parts may be equal, and is the count still given by a finite linear recurrence?

Key concepts: generating function, composition, linear recurrence, rational function.