Consider a set S of the first 10 natural numbers.Find the number of subsets that do not contain consecutive elements.
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 atleast 2 adjacent numbers.
The total comes out to be 144
Strategy:
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 atleast 2 adjacent numbers.
The total comes out to be 144
No comments:
Post a Comment