Задача
COM-B2-M09-P008 Композиции из единиц и двоек
#8
★★★☆☆ Уровень 3 из 5
Пусть \(c_n\) - число упорядоченных представлений числа \(n\) в виде суммы слагаемых \(1\) и \(2\). Найдите производящую функцию \(C(x)=\sum_{n\ge 0}c_nx^n\) и выразите \(c_n\) через числа Фибоначчи.
Разбейте композиции по первому слагаемому.
Пустая композиция для \(0\) дает \(c_0=1\). Для \(n\ge 2\) первая часть равна \(1\) или \(2\), значит, \(c_n=c_{n-1}+c_{n-2}\), причем \(c_1=1\). Для ряда получаем \(C(x)=1+xC(x)+x^2C(x)\), откуда \(C(x)=\frac{1}{1-x-x^2}\). Если \(F_0=0\), \(F_1=1\), то \(c_n=F_{n+1}\).
Важно различать композиции, где порядок слагаемых важен, и разбиения.