Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Example: I have a set {a,b,c}. I want to know how many different sets could I get from these elements. -Ex: {a,b} , {a,c} , {a}, {b} , {c} , {b,c} and {a,b,c} itself

Which is the algorithm ? and which theory is this?

share|improve this question

2 Answers 2

Given a set with $n$ elements it has $2^n$ subsets, and $2^n-1$ non-empty subsets.

You can prove this by induction, in fact this is one of the standard examples for induction.

In your example you have $\{a,b,c\}$ which are $3$ elements, and therefore $2^3-1=7$ non-empty subsets.

share|improve this answer

You are "computing" the so-called powerset of the initial set. Each element (of the original set) can or cannot be chosen in a possible subset. If you start with $n$ elements that are $n$ yes/no choices, so $2^n$ possible subsets. That includes the all-no sequence of choices, or the emptyset $\varnothing$.

I guess that is the algorithm you want to have. If you know binary numbers, listing them is as listing subsets. In your example 000, 001, 010, 011, 100, \dots, 111 form $\varnothing$, $\{a\}$, $\{b\}$, $\{b,a\}$, $\{c\}$, $\{c,a\}$, $\{c,b\}$, $\{c,b,a\}$. Done. Silly order in the sets, but I wanted to stay close to the order I took for the bits: cab.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.