1
$\begingroup$

I remember some things from college about computing permutations and combinations, but I don't really recall if we ever learned any alternative to the formula I'm about to describe. In this case, I want to know how many full combinations (the nomenclature is probably not correct) you can generate from a set of n elements. That is, from n elements, you may choose 1, 2, 3, ... all the way up to choosing all n.

I think that this formula does the trick, but is there any simpler alternative? Specifically, I'd rather have a non-iterative one (without the sum loop). Ideas?

$\endgroup$
1
  • $\begingroup$ If "combinations" means "subsets", then, as Marcus Stuhr answered, it's $2^n$. Page 30 here: [books.google.com/… $\endgroup$
    – avs
    May 3, 2017 at 19:53

1 Answer 1

Reset to default
2
$\begingroup$

Via binomial theorem:

$$\sum_{k=0}^{n} \binom{n}{k} = \sum_{k=0}^{n} \binom{n}{k} (1)^{n-k}(1)^k = (1+1)^n = 2^n$$

If you aren't counting the $k=0$ case then you subtract $1$ from this.

$\endgroup$
2
  • $\begingroup$ Ah, it does ring a bell :) thank you! $\endgroup$
    – André Fratelli
    May 4, 2017 at 9:25
  • $\begingroup$ why do you put one and one then factor it? $\endgroup$
    – nutella_eater
    Mar 11, 2021 at 18:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .