Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers

up vote 4 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|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
2  
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
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. –  JBC Jun 22 '12 at 10:20
add comment

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|improve this answer
1  
Wish I could upvote this answer twice. Thanks much. That table REALLY helped. –  marcamillion Jun 22 '12 at 8:59
1  
@marcamillion glad to help :) –  E.O. Jun 22 '12 at 9:00
add comment

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

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|improve this answer
    
This is the same answer as that given by fretty –  Willie Wong Jul 11 '13 at 8:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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