MathDB
Counting subsets

Source: AMC 12 2006A, Problem 25

February 5, 2006
countingdistinguishabilityprobabilitybinomial coefficientsAMC

Problem Statement

How many non-empty subsets S S of {1,2,3,,15} \{1, 2, 3, \ldots, 15\} have the following two properties? (1) No two consecutive integers belong to S S. (2) If S S contains k k elements, then S S contains no number less than k k. <spanclass=latexbold>(A)</span>277<spanclass=latexbold>(B)</span>311<spanclass=latexbold>(C)</span>376<spanclass=latexbold>(D)</span>377<spanclass=latexbold>(E)</span>405 <span class='latex-bold'>(A) </span> 277\qquad <span class='latex-bold'>(B) </span> 311\qquad <span class='latex-bold'>(C) </span> 376\qquad <span class='latex-bold'>(D) </span> 377\qquad <span class='latex-bold'>(E) </span> 405