PUMaC 2009 · 组合（B 组） · 第 2 题

PUMaC 2009 — Combinatorics (Division B) — Problem 2

Find the number of subets of { 1,2, . . . ,7 } that do not contain two consecutive integers.

解析

Find the number of subets of { 1,2, . . . ,7 } that do not contain two consecutive numbers. Solution. 34. Let a be the number of subsets of { 1,2, . . . , n } that don’t contain consecutive n numbers. If a subset contains n , then it doesn’t contain n − 1, and then it can be anything counted by a . If it doesn’t contain n , then it is something counted by a , and it is clear n − 2 n − 1 that anything counted by a arises from precisely one thing counted by a or a , so we n n − 1 n − 2 get a = a + a . It is easy to check a = 2 and a = 3, and then it is a quick jaunt to n n − 1 n − 2 1 2 a = 34. 7