Calculating Number of Possible Subsets of a Set

Date: 06/14/2002 at 14:57:35
From: Jim
Subject: calculating number of possible sets of a subset


What is the formula for calculating the number of posssible subsets 
for a finite set?

For Example:  A set of a total of 5.  1-5  Subsets with at least 
three integers, i.e. 1,2,3; 1,2,4; etc. The total possible 
combinations of these subsets is 10. What is the formula to 
calculate this equation?

123 234 345
124 235
125 245  
134 
135 
145

Date: 06/14/2002 at 22:37:09
From: Doctor Carbon
Subject: Re: calculating number of possible sets of a subset


Hi Jim,

Here's my way of looking at this problem:

If I want all the subsets of a certain size m out of a set with n 
distinct elements, then the formula for that is the same as 
finding the binomial coefficient. (See 
 
    http://mathworld.wolfram.com/BinomialCoefficient.html 


for a formal description).

In your case, as you correctly pointed out, there are 10 ways of 
picking subsets of size 3 from a set of size 5. The formula for 
calculating the coefficient is:

               n!
  C(n,m) = -----------
           m! (n - m)! 

where n! is n factorial and is equal to n*(n-1)*(n-2)*....*2*1.

Note that the Ask Dr. Math FAQ has a terrific explanation for why 
this works, at

    http://mathforum.org/dr.math/faq/faq.comb.perm.html 

If we want a formula that finds ALL the subsets of a set of size 
5 (including the null set, subsets of size 1, subsets of size 2, 
etc.), then I think the best way would be to list them separately:

    1      [null set] 
  + C(5,1) [subsets of size 1]
  + C(5,2) [subsets of size 2]
  + ...
  + C(5,5) [subsets of size 5]

In this case the result would be 1 + 5 + 10 + 10 + 5 + 1, which 
is 32.

Interestingly (and this is in the FAQ too), this is the same as 
the 5th row in Pascal's Triangle (see 

    http://mathworld.wolfram.com/PascalsTriangle.html  

for more on this).

Whenever I see a number like 32, I usually check to see if there 
is a "power of 2" pattern.

So, if we do the same exercise for all the subsets of a set of 
size 4, we get 1 + 4 + 6 + 4 + 1, which is 16. This is the same 
as 2^4.
 
The previous answer was 32, which is 2^5. This suggests that 
there IS a pattern. You can confirm the pattern (that sets of 
size n have 2^n subsets) for different numbers, although that 
would not constitute a rigorous proof, and would be frowned upon 
by math purists, I suspect :-).

Hope this helps. Please feel free to write back if it doesn't, or 
if you have any other questions.
 
- Doctor Carbon, The Math Forum
  http://mathforum.org/dr.math/