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.

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. Jun 22 '12 at 8:59
• @marcamillion glad to help :)
– E.O.
Jun 22 '12 at 9:00
• 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? Aug 16 '18 at 21:30

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

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. Jun 22 '12 at 13:55