# What is the total number of combinations of 5 items together when there are no duplicates?

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.

-

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

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

-
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

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.

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

-

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

-
This is the same answer as that given by fretty – Willie Wong Jul 11 '13 at 8:14