11
$\begingroup$

I have 5 categories - A, B, C, D & E.

I want to basically create groups that reflect every single combination of these categories without there being duplicates.

So groups would look like this:

  • A
  • B
  • C
  • D
  • E
  • A, B
  • A, C
  • A, D
  • A, E
  • B, C
  • B, D
  • B, E
  • C, D . . . etc.

This sounds like something I would use the binomial coefficient $n \choose r$ for, but I am quite fuzzy on calculus and can't remember exactly how to do this.

Any help would be appreciated.

Thanks.

$\endgroup$
23
$\begingroup$

Let $$nCr=\binom{n}{r}=\frac{n!}{k!(n-k)!}$$ Remember that the $\frac{n!}{(n-k)!}$ gives all the permutations and the $k!$ in the denominator is what disregards duplicates.

Now; you want all the ways you can choose $$(1 \text{ category from } 5) + (2 \text{ category from } 5) + \dots + (5 \text{ category from } 5)$$ i.e. $$\binom{5}{1}+\binom{5}{2}+\binom{5}{3}+\binom{5}{4}+\binom{5}{5}=2^5-1=31$$ Note that this follows from the fact that $$(1+1)^n=\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n-1}+\binom{n}{n}=2^n$$ Subtracting $\binom{n}{0}$ from both sides gives us $$\binom{n}{1}+\cdots+\binom{n}{n-1}+\binom{n}{n}=2^n-\binom{n}{0}$$ But since $\binom{n}{0}=1,\forall n\in\mathbb{N}$ we have that $$\binom{n}{1}+\cdots+\binom{n}{n-1}+\binom{n}{n}=2^n-1$$ When $n=5$ we thus get the above answer.

Addendum: To address your concern that there seems to be more than $31$ combinations, here is a list of all the possibilities: $$\begin{array}{|c|c|c|c|c|c|c|} & 1 \text{ category} & 2 \text{ categories} & 3 \text{ categories} & 4 \text{ categories} & 5 \text{ categories} & \text{Sum}\\ \hline & A & AB & ABC & ABCD & ABCDE\\ \hline & B & AC & ABD & ABCE \\ \hline & C & AD & ABE & ABDE \\ \hline & D & AE & ACD & ACDE \\ \hline & E & BC & ACE & BCDE \\ \hline & & BD & ADE \\ \hline & & BE & BCD \\ \hline & & CD & BCE \\ \hline & & CE & BDE \\ \hline & & DE & CDE \\ \hline \text{Total} & 5 & 10 & 10 & 5 & 1 & 31 \\ \hline \end{array}$$

$\endgroup$
3
  • 1
    $\begingroup$ Wish I could upvote this answer twice. Thanks much. That table REALLY helped. $\endgroup$ Jun 22 '12 at 8:59
  • 1
    $\begingroup$ @marcamillion glad to help :) $\endgroup$
    – E.O.
    Jun 22 '12 at 9:00
  • $\begingroup$ I just want to make sure I am understanding this correctly (I too am fuzzy and trying to recall) if I want to know what all the combinations of days in the week are then I would just do: 2^7 - 1 = 127? I keep getting terribly confused as to when I should use factorials, correct me if I am wrong but 7! would be used to find the permutations, not the combinations? $\endgroup$ Aug 16 '18 at 21:30
12
$\begingroup$

There are $\binom{5}{1}$ combinations with 1 item, $\binom{5}{2}$ combinations with $2$ items,...

So, you want : $$\binom{5}{1}+\cdots+\binom{5}{5}=\left(\binom{5}{0}+\cdots+\binom{5}{5}\right)-1=2^5-1=31$$

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

$\endgroup$
5
  • $\begingroup$ You know...that was my initial inclination - but then I started writing them out and it seems like there would be more than 31 combinations. What's this theory called? Or is there no name? $\endgroup$ Jun 22 '12 at 8:32
  • $\begingroup$ I think it's simply combinatorics. $\endgroup$
    – JBC
    Jun 22 '12 at 8:36
  • $\begingroup$ Why do you subtract the 1 at the end? Also, can you explain the theory of why the combination with 3 items will be the same as the combination with 2 items...that seems counter-intuitive. $\endgroup$ Jun 22 '12 at 8:37
  • 2
    $\begingroup$ 1) I substracted $\binom{5}{0}=1$ to use the formula recalled at the end (Notice that the formula begins by $\binom{5}{0}$ but your sum by $\binom{5}{1}$). 2) $\binom{n}{k}$ is the number of subset of $\{1,\ldots,n\}$ with $k$ elements, ie the number of choices to take $k$ elements from a set of $n$ elements without repetition, you can show that $\binom{n}{k}=\binom{n}{n-k}$ using $\binom{n}{k}=\frac{n!}{k!(n-k)!}$. $\endgroup$
    – JBC
    Jun 22 '12 at 8:44
  • 1
    $\begingroup$ And I think that this formula is intuitive : chosing the k items we take, it's the same thing as choosing the n-k items we left. $\endgroup$
    – JBC
    Jun 22 '12 at 10:20
10
$\begingroup$

Think about this from another angle. You want some number of these five categories without repetition.

Well each category is either chosen by you or not chosen by you. Each such choice bears no relationship with the other choices.

Thus there are $2^5 = 32$ possibilities. However, you are not counting the choice of none of the five categories, so we subtract $1$ to get $31$ possibilities.

$\endgroup$
1
  • 1
    $\begingroup$ I think this is the most intuitive way to formualate the solution, and the $2^n$ formula is more natural than when presented in @JBC's answer. $\endgroup$ Jun 22 '12 at 13:55
1
$\begingroup$

Use binary! 1, 2, 4, 8, 16 adds up to 31
The number of combinations with 6 numbers would be 63
Seven digits would be 127, etc.

$\endgroup$
0
$\begingroup$

I appreciate the math that got you to the answer, but if you look at the problem as binary numbers, 0-not used, 1-used, and each bit position as an item, you arrive at the same conclusion...for N bits, how many values can you encode? Not counting the 0 value. A__ = 100 (high order position is 1) B = 010 AB_ = 110 __C = 001 A_C = 101 _BC = 011 ABC = 111

$\endgroup$
1

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