Find the number of sets A such that A ⊂ {1, 2, 4, 5, 6, 8, 9, 10, 11}, |A| = 4 and A contains no consecutive integers.
This is a PENCIL AND PAPER PROBLEM! What's with all the computer solutions?
So lets start by actually analyzing set A. A can be partitioned into three runs of consecutive numbers: B={1,2} C={4,5,6} and D= {8,9,10,11}.
The desired subsets can have at most one member form B, at most two members from C, and at most two members from D.
We seek a subset of A of size 4, so those four members can be dived among B, C, and D in three ways:
* one member of B, one member of C and two members of D
* one member of B, two members of C and one member of D
* zero members of B, two members of C and two members of D
There is one way to choose no members from B
There are two ways to choose one member of B
There are three ways to choose one member of C
There is one way to choose two nonconsecutive members of C
There are four ways to choose one member of D
There are three ways to choose two nonconsecutive members of D.
Then the final calculation is 2*3*3 + 2*1*4 + 1*1*3 = 18+8+3 = 29.
Analytic Solution
