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.
$\endgroup$5 Answers
$\begingroup$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}$$
$\endgroup$ 3 $\begingroup$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$$
$\endgroup$ 5 $\begingroup$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.
$\endgroup$ 1 $\begingroup$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
$\endgroup$ 1
