HMMT 二月 2012 · COMB 赛 · 第 3 题

3. In the figure below, how many ways are there to select 5 bricks, one in each row, such that any two bricks in adjacent rows are adjacent? Answer: 61 The number of valid selections is equal to the number of paths which start at a top brick and end at a bottom brick. We compute these by writing 1 in each of the top bricks and letting lower bricks be the sum of the one or two bricks above them. Thus, the number inside each brick is the number of paths from that brick to the top. The bottom row is 6, 14, 16, 15, 10, which sums to

1 1 1 1 1 2 2 2 2 1 2 4 4 4 3 6 8 8 7 3 6 14 16 15 10