Задача
COM-B2-M09-P016 Ровно k домино
#16
★★★★☆ Уровень 4 из 5
Полоску \(1\times n\) покрывают клетками \(1\times 1\) и домино \(1\times 2\). Докажите, что число покрытий с ровно \(k\) домино равно \(\binom{n-k}{k}\).
После сжатия каждого домино в один блок всего получается \(n-k\) блоков.
Если в покрытии ровно \(k\) домино, то оставшихся одиночных клеток \(n-2k\). Сожмем каждое домино в один блок. Тогда всего блоков \(k+(n-2k)=n-k\), и нужно выбрать, какие \(k\) из них являются домино. Это можно сделать \(\binom{n-k}{k}\) способами. Обратное восстановление однозначно: выбранные блоки разворачиваются в домино, остальные остаются одиночными клетками.
Можно также вывести через рекуррентность \(T_n(y)=T_{n-1}(y)+yT_{n-2}(y)\).