Skip to content

Counting domino coverings of a two-row strip

Question

In how many ways can a board with 22 rows and nn columns be covered exactly by 1×21\times2 dominoes?

Short answer

Fn+1F_{n+1}, the (n+1)(n+1)-th Fibonacci number (1,2,3,5,8,…1,2,3,5,8,\dots for n=1,2,3,…n=1,2,3,\dots). Look at the left end: either one vertical domino fills column 11, leaving Tn−1T_{n-1} ways, or two stacked horizontal dominoes fill columns 11-22, leaving Tn−2T_{n-2}. So Tn=Tn−1+Tn−2T_n=T_{n-1}+T_{n-2} with T1=1T_1=1, T2=2T_2=2.

Adapted from Joshi, Denson & Downes, Quant Job Interview Questions and Answers, Q8.14, p.277; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free