Problem
COM-B2-M09-P008 Compositions Using Ones and Twos
#8
★★★☆☆ Level 3 of 5
Let \(c_n\) be the number of ordered representations of \(n\) as a sum of parts \(1\) and \(2\). Find the generating function \(C(x)=\sum_{n\ge 0}c_nx^n\) and express \(c_n\) using Fibonacci numbers.
Split the compositions by their first part.
The empty composition of \(0\) gives \(c_0=1\). For \(n\ge 2\), the first part is \(1\) or \(2\), so \(c_n=c_{n-1}+c_{n-2}\), with \(c_1=1\). For the series, \(C(x)=1+xC(x)+x^2C(x)\), hence \(C(x)=\frac{1}{1-x-x^2}\). If \(F_0=0\), \(F_1=1\), then \(c_n=F_{n+1}\).
Important distinction: in compositions, the order of parts matters; in partitions, it does not.