10
$\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.

5 Answers 5

0

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

  • 0
    This is the same answer as [that given by fretty](http://math.stackexchange.com/a/161574/1543)2013-07-11
21

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}$

  • 0
    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?2018-08-16
10

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$

  • 1
    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.2012-06-22
9

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.

  • 1
    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.2012-06-22
1

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.