HMMT 二月 2002 · 冲刺赛 · 第 15 题

英文解析

15. How many sequences of 0 s and 1 s are there of length 10 such that there are no three
    0 s or 1 s consecutively anywhere in the sequence?
    Solution: We can have blocks of either 1 or 2 0 s and 1 s, and these blocks must bealternating between 0 s and 1 s. The number of ways of arranging blocks to form a sequenceof length n is the same as the number of omino tilings of a 1-by- n rectangle, and we maystart each sequence with a 0 or a 1, making 2 F or, in this case, 178 sequences. n