2
$\begingroup$

How many combinations do I get for 5 Items A,B,C,D,E if I allow pairs, triples, quadrouples:

AB, AC, .. BC, BD, ..

ABC, ABD, ABE, .. BCD, ..

ABCD, ABDE, BCDE

ABCDE

The combination AC is the same as CA. However, there are no AA or CC combinations.

What's the formula for this with n items that can be aranged in groups the size of 2 to n?

  • 0
    $\displaystyle \sum_{k=2}^n \binom {n}{k}=2^n-n-1$2012-04-12

1 Answers 1

4

Let $S$ be a set with $n$ elements. You are asking how many subsets of $S$ there are, that contain anywhere from $2$ to $n$ elements.

The set $S$ has $2^n$ subsets. But these include the empty set, and $n$ one-element subsets. Take these away, and we are left with $2^n-n-1$.

Remark: For any fixed $k$, the number of $k$-element subsets of $S$ is $\binom{n}{k}$, where $\binom{n}{k}=\frac{n!}{k!(n-k)!}$.