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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.