Home > Just Math
| Easy count (Posted on 2014-07-29) |
 |
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}.
|
|
Submitted by Ady TZIDON
|
|
No Rating
|
|
|
Solution:
|
(Hide)
|
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.)
|
|
Please log in:
Forums (1)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
