Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Logic
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search