Problem
COM-B2-M09-P016 Exactly k Dominoes
#16
★★★★☆ Level 4 of 5
A \(1\times n\) strip is tiled by \(1\times 1\) squares and \(1\times 2\) dominoes. Prove that the number of tilings with exactly \(k\) dominoes is \(\binom{n-k}{k}\).
After compressing each domino into one block, there are \(n-k\) blocks in total.
If a tiling has exactly \(k\) dominoes, then the number of single squares is \(n-2k\). Compress each domino into one block. Then there are \(k+(n-2k)=n-k\) blocks in total, and we only need to choose which \(k\) of them are dominoes. This can be done in \(\binom{n-k}{k}\) ways. The reconstruction is unique: chosen blocks expand into dominoes, and the others remain single squares.
Can also be derived from the recurrence \(T_n(y)=T_{n-1}(y)+yT_{n-2}(y)\).