Number of Subsets without consecutive elements

Problem

Consider a set S of the first 10 natural numbers.Find the number of subsets that do not contain consecutive elements.

Solution

The question is based on pure calculation and some combinatorics.

Subsets of length 0 = 1
Subsets of length 1 = 10
These two cases are straight forward.

Subsets of length 2 = number of ways we can pick two numbers out of 10 - number of ways in which we can pick two adjacent numbers
= 10 C 2 - 9= 45-9=36

Subsets of length 3 = the number of ways we can pick 3 numbers out of 10 - number of ways we can pick 3 numbers having 2 adjacent numbers - number of combinations where all 3 are adjacent i.e.
= 10 C 3 - 56 - 8

The latter case is simple but think over why number of combinations that have two adjacent numbers are 56, there are two special cases to be considered, one where adjacent numbers are in between like 5,6 and the other where they are at boundary i.e. 0,1

similarly
Subsets of length 4 = 35
Subsets of length 5 = 6

We cannot go beyond this because then we will have at-least 2 adjacent numbers.

The total comes out to be 144

References

• http://sudhansu-codezone.blogspot.in/2012/07/subsets-without-consecutive-elements.html