邮递员要给街道上的19间房子送邮件．他发现在同一天中，没有两间相邻的房子都收到邮件，且连续三间房子中至少有一间会收到邮件．求有多少种可能投递邮件的情况？
【难度】
【出处】
2001年第19届美国数学邀请赛Ⅰ（AIMEⅠ）
【标注】
【答案】
351
【解析】
考虑由0或者1组成的 $n$ 位的串，0和1分别代表没有收到邮件和收到邮件．题目是要求我们求出不包含有11和000的串的个数．$n$ 位的串中最后两位数不能是11，可以是00，01，10．设 ${{a}_{n}}$ 代表以00结尾的中的个数，设 ${{b}_{n}}$ 代表以 $01$ 结尾的串的个数，设 ${{c}_{n}}$ 代表以10结尾的串的个数．如果 $n$ 位的串以00结尾，则00前面的数位一定是1，且 $n-1$ 位的串的最后两位将是10，所以 ${{a}_{n}}={{c}_{n-1}}$；如果 $n$ 位的串以01结尾，则01前面的数可以是1也可以是0，且 $n-1$ 位的串的最后两位将是00或10，所以 ${{b}_{n}}={{a}_{n-1}}+{{c}_{n-1}}$；如果 $n$ 位的串以10结尾，则10前面的数一定是0，且 $n-1$ 位的串的最后两位将是01，所以 ${{c}_{n}}={{b}_{n-1}}$．显然，${{a}_{2}}={{b}_{2}}={{c}_{2}}=1$，利用递推等式和初始值，我们可以计算出 ${{a}_{19}}+{{b}_{19}}+{{c}_{19}}=86+151+114=351$．
答案
解析
备注
