2
$\begingroup$

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, \ldots, 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)!}$.

2 Answers 2

5

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.

  • 0
    @All, thank you! Unfortunately I don't have enough reputation to up vote both of the answers (I will if I can someday).2011-06-03
1

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.

  • 0
    @All: can someone explain the downvote?2011-06-03