Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
up vote 5 down vote accepted

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

share|cite|improve this answer
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? – marcamillion Jun 22 '12 at 8:32
I think it's simply combinatorics. – JBC Jun 22 '12 at 8:36
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. – marcamillion Jun 22 '12 at 8:37
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)!}$. – JBC Jun 22 '12 at 8:44
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. – JBC Jun 22 '12 at 10:20

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

share|cite|improve this answer
Wish I could upvote this answer twice. Thanks much. That table REALLY helped. – marcamillion Jun 22 '12 at 8:59
@marcamillion glad to help :) – E.O. Jun 22 '12 at 9:00

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.

share|cite|improve this answer
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. – Joshua Shane Liberman Jun 22 '12 at 13:55

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.

share|cite|improve this answer

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

share|cite|improve this answer
This is the same answer as that given by fretty – Willie Wong Jul 11 '13 at 8:14

protected by Community Mar 1 at 23:39

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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