Here's a simple question that popped into my head. I shouldn't be struggling with but am.
Suppose there are $n$ objects. We want to find the number of distinct groups.
First let's take the case where each of the $n$ objects is distinct. The number of distinct groups should be just $2^n$ right?
Here's where I get tripped up. Let's say all of the items are distinct except we have 1 item that is repeated. Let's say $\text{item}_1$ and $\text{item}_2$ are identical to each other. Well now the answer is not $2^n$ anymore because having $\text{item}_1$ and not $\text{item}_2$in my group is the same as having $\text{item}_2$ and not $\text{item}_1$. But having both and neither of the items should count as separate groups…
Does that make sense?
So let's break this into cases –
We have $\text{item}_1$ but not $\text{item}_2$. There are $2^{n-2}$ in this case because the number of distinct groups from the $n-2$ objects left is $2^{n-2}$
We have both $\text{item}_1$ and $\text{item}_2$. Again there are $2^{n-2}$ distinct groups in this case.
Now the case for neither of the items. Again there are $2^{n-2}$ distinct groups in this case.
We ignore the case where we have $\text{item}_2$ but not $\text{item}_1$ since we have already accounted for that in the first case and because the two items are identical.
How many distinct groups are there? There should be $3 (2^{n-2})$ since we just have to sum all three cases together.
Is this correct? How would I expand this for the general case where I have $k$ identical objects of one item in n objects. How about if I had $k_1, …, k_r$ identical objects for items $1, …, r$ amongst the n objects.
Going back to my example, I feel like back in highschool what I would do is just take the number of distinct n groups form before, $2^n$, and divide it by $2$ since I double counted one of the items. Why is this wrong or correct?
Also a general question – How can I tell when I've fully counted everything the correct number of times correctly. Any tips, resources, tricks and pointers are greatly appreciated. 🙂
Best Answer
It would be better to call these "sets" or "multisets" because "group" has a technical meaning in mathematics.
Suppose you have $c_k$ copies of each item $k$, and let $x_k \in \{0,\dots,c_k\}$ be the number of copies you select. The choices are independent, and you have $c_k+1$ choices for each item, so the total number of distinct multisets is $$\prod_{k=1}^n (c_k+1).$$
In the special case $c_k=1$ (all items are distinct), this product simplifies to $$\prod_{k=1}^n (c_k+1)=\prod_{k=1}^n (1+1) = 2^n.$$
In the special case $c_1=0$, $c_2=2$, and $c_k=1$ for $k>2$, this product simplifies to $$\prod_{k=1}^n (c_k+1)=(0+1)(2+1)\prod_{k=3}^n (1+1) = 3\cdot 2^{n-2}.$$
In the special case $c_1=n$ and $c_k=0$ for $k>1$ (all items are the same), this product simplifies to $$\prod_{k=1}^n (c_k+1)=(n+1)\prod_{k=2}^n (0+1) = n+1.$$
By the way, the general formula also counts the number of divisors of an integer whose prime factorization is of the form $$p_1^{c_1} p_2^{c_2} \dots p_n^{c_n}.$$ The "items" are the primes, and the numbers of copies selected are the numbers of times each prime appears in the divisor. See https://oeis.org/A000005.