Simple Combination Formula

Sorry for this simple question:

I'm looking for the formula to calculate all the possible combinations from a set of n numbers, where you can select r numbers at once where r can be 0, 1, ..., n-1, n (no repetition, and order not important $\{a,b\} = \{b,a\}$?

As an example I have 3 objects (a,b,c) and all their possible combinations are (for a total of 8):

• none selected
• a
• a,b
• a,b,c
• a,c
• b,c
• b
• c

I need the formula, something like $\frac{(n+r-1)!}{n!(r-1)!}$.

Thank you

-

By the binomial theorem, $$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{r=0}^{n}\binom{n}{r}=\sum_{r=0}^{n}\binom{n}{r}1^r1^{n-r}=(1+1)^n=2^n.$$ However, a more intuitive way to think about this is to consider each of the $n$ elements. If you want to take some combination of elements from your set, you could line up all your elements, and for each one, choose to pick it up or not. So you have $2$ choices for what to do with each of the $n$ elements, giving a total of $2^n$ ways to choose all the possible subsets, or as you say, combinations.

-
Hi @mixedmath, I originally posted something of this form as a comment, but then thought I would expand it to an answer once I read Radu's user profile. The info there makes me doubt he is a student, so based on that, I intended to fully answer the question. –  yunone Jun 3 '11 at 9:39
You are absolutely right. One quick look at the profile, and I agree. He has also posted on my response as well. –  mixedmath Jun 3 '11 at 9:43
@All, thank you! Unfortunately I don't have enough reputation to up vote both of the answers (I will if I can someday). –  Radu Maris Jun 3 '11 at 9:49

If this is homework, than I greatly regret posting this answer. I expect you to say so immediately, and I will consider the repercussions later.

What you should do is consider summing the standard combination forms - for example, on 3 objects, we are counting the sum of the situations when you take: 0 of them, 1 of them, 2 of them, and all of them. But if we take 2 of them, we know there are $3 \choose 2$ different ways to do this. In general, choosing k of n objects can be done in $n \choose k$ - hence the semantic phrasing "n choose k."

So a naive answer would be to simply sum these. But you'll notice a pattern if you do this. In fact, I won't explicitly answer what this is, but instead I'll encourage you to try it out. But I'll explain why it's true.

I will assume that you are familiar with the binomial theorem and its relationship to combinations; then you also know that we are really considering the coefficients of $(x+y)^n$. If we want to sum the coefficients, there is no reason not to just let $x = y = 1$, so that the coefficients are always multiplied by 1 according to the theorem...

And from a little experimentation and the above paragraph, I think you will find what you need.

EDIT: While I like this answer because it gives a good understanding behind the combinatorial aspect of the question, one could also simply consider whether each element is in the set. So there are 2 possibilities for each element...

Note: If this is homework, please add that tag. I am changing your tags a little bit on this question, as I don't think it's a linear algebra question.

-
Not homework, I'm not a student anymore, just that I allways have a pen and paper and draw all posible combination to find the answer, so i thought there sure must be an easy "mathematical" way of doing this, so I asked :) –  Radu Maris Jun 3 '11 at 9:39
@Radu: That's great! Keep up the mathematical play. –  mixedmath Jun 3 '11 at 9:43
@All: can someone explain the downvote? –  mixedmath Jun 3 '11 at 9:44