Would you count it manually?
Probability
Level
4
How many subsets of don't contain any consecutive integers?
The answer is 32951280099.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
let A(n) be the number of subsets of {1,2,3,...,n} which don't contain any consecutive integers.
A(0)=1 as it is simply the empty set A(1)=2 as it is all subsets namely {},{1}
now for n>=2, consider two instances for a given subset
1) n is in the subset, if this is the case then n-1 can not be in the subset and any valid subset of {1,2,...,n-2} will work for the remaining elements of the subset, thus there are A(n-2) valid subsets which contain n.
2) n is not in the subset, then this is simply the case for {1,2,...,n-1} which is simply A(n-1)
Thus A(n)=A(n-2)+A(n-1) with A(0)=1 and A(1)=2 or in other words it is simply a shifted Fibonacci sequence and the usual methods can be used to complete A(50)