I have been doodling around and have stumbled across the following problem:
Say I have a set $p = \{p_1, p_2, p_3, ..., p_n\}$ where $p_i \in \mathbb{N}$
$p_i$ could represent the amount of a distinct object i.e $p_1 =$ amount of red balls and $p_2 =$ amount of blue balls and so on.
Now to calculate how many distinct possible ways I could choose a new set of balls would be:
$\prod\limits_{i=1}^n (p_i + 1) $
Yet I thought to myself it should also be possible to represent this in terms of combinations:
$\sum\limits_{i=1}^n\binom {\sum\limits_{i=1}^n p_i} i $
This would work perfectly fine if all the elements are equal to 1 yet when $p_i > 1$ then the above would count duplicate sets. So I need to determine a way to get rid of all the duplicate sets. I tried counting all the different combinations of an element and multiplying it through with all the different combinations of the other elements, but things get messy and I am not sure if this is the right approach. Any ideas?
Let's start with a concrete example.
Let's say we have five red balls, six blue balls, and seven green balls. If we wish to arrange all $18$ balls in a row, we can first choose $5$ of the $18$ positions for the red balls in $\binom{18}{5}$ ways, then choose $6$ of the remaining $13$ positions for the blue balls in $\binom{13}{6}$ ways, forcing us to fill the remaining seven positions with green balls in $\binom{7}{7} = 1$ ways. The number of ways we can arrange the five red balls, six blue balls, and seven green balls is $$\binom{18}{5}\binom{13}{6}\binom{7}{7} = \frac{18!}{13!5!} \cdot \frac{13!}{7!6!} \cdot \frac{7!}{0!7!} = \frac{18!}{5!6!7!0!} = \frac{18!}{5!6!7!}$$ since $0! = 1$. Note that $5 + 6 + 7 = 18$. Moreover, observe that for a particular arrangement, we can permute the $5$ red balls in $5!$ ways, the six blue balls in $6!$ ways, and the seven green balls in $7!$ ways without changing the ways the balls of different colors are arranged in the row.
More generally, if we have $p_1$ balls of type $1$, $p_2$ balls of type $2$, $\ldots$, and $p_n$ balls of type $n$ such that $$p = p_1 + p_2 + \cdots + p_n$$ the number of distinguishable ways to arrange the balls is \begin{align*} \binom{p}{p_1}&\binom{p - p_1}{p_2}\binom{p - (p_1 + p_2)}{p_3} \cdots \binom{p - (p_1 + p_2 + \cdots + p_{n - 1})}{p_n}\\ & = \frac{p!}{(p - p_1)!p_1!} \cdot \frac{(p - p_1)!}{[p - (p_1 + p_2)]!p_2!} \cdot \frac{[p - (p_1 + p_2)]!}{[p - (p_1 + p_2 + p_3)]!p_3!} \cdots \frac{[p - (p_1 + p_2 + \cdots + p_{n - 1})]!}{[p - (p_1 + p_2 + \cdots + p_{n - 1} + p_n)]!p_n!}\\ & = \frac{p!}{(p - p_1)!p_1!} \cdot \frac{(p - p_1)!}{[p - (p_1 + p_2)]!p_2!} \cdot \frac{[p - (p_1 + p_2)]!}{[p - (p_1 + p_2 + p_3)]!p_3!} \cdots \frac{[p - (p_1 + p_2 + \cdots + p_{n - 1})]!}{0!p_n!}\\ & = \frac{p!}{p_1!p_2!p_3! \cdots p_n!} \end{align*} Note that the denominator accounts for the number of ways we could permute balls of the same color without changing the overall arrangement of the balls of different colors in the row.
The number $$\binom{p}{p_1, p_2, \ldots, p_n} = \frac{p!}{p_1!p_2! \cdots p_n!}$$ is called a multinomial coefficient since it corresponds to the coefficient of $$x_1^{p_1}x_2^{p_2} \cdots x_n^{p_n}$$ in the expansion of $$(x_1 + x_2 + \cdots + x_n)^p$$ where $p_1 + p_2 + \cdots + p_n = p$.
Note that when $n = 2$, the multinomial coefficient reduces to the binomial coefficient $$\binom{p}{p_1} = \frac{p!}{p_1(p - p_1)!} = \frac{p!}{p_1!p_2!}$$ since $p_1 + p_2 = p$.