Let S be a set of some positive integers. We'll call S autonomous if the number of elements in S is itself an element of S. e.g. the set {2,3,5} is autonomous, as is the set {2,7}, but the sets {1, 4} or {2,4,5} are not.

Determine a general formula for the number of autonomous subsets of {1, 2, 3, ... , n}.

The subset of k numbers must consist of the number k itself + any subset of n-1 members other than k, i.e. one of C(n-1, k-1) possible combinations.
Summing for all possible values of k (1 to n-1):
Sum=C(n-1,0)+ C(n-1,1)+ C(n-1,2)+... C(n-1, n-1)
=2^(n-1).

Comments: (
You must be logged in to post comments.)