3
$\begingroup$

Let's say you have a number of groups that contain a variable amount of elements. For example, taking colored balls and assume you have $3$ different groups of those, consisting of the following items:

Group 1: Black ball $1$, Black ball $2$, Black ball $3$

Group 2: Orange ball $1$

Group 3: Yellow ball $1$, Yellow ball $2$, Yellow ball $3$, Yellow ball $4$

Now I'm interested in forming a group that has $k$ elements in total, for example $4$; so I want to form groups consisting of no more and no less than $4$ balls in total.

How many ways are there to form such groups, given the available colored balls? For example, one result might be:

Orange ball $1$, Yellow ball $1$, Yellow ball $2$, Black ball $1$

The colors themselves are not distinguishable, so this outcome should be the same as Orange ball $1$, Yellow ball $1$, Yellow ball $3$ (!), Black ball $1$ for example, and hence not be counted again.

Thanks!

$\endgroup$

closed as off-topic by Shaun, ahulpke, JMP, TheSimpliFire, Claude Leibovici Mar 5 '18 at 8:51

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Shaun, ahulpke, JMP, TheSimpliFire, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. $\endgroup$ – José Carlos Santos Mar 4 '18 at 14:56
  • $\begingroup$ Thank you! Unfortunately, I don't really know how to approach this one anymore - have been dealing with combinatorics last 10 years ago, and this is a small part of a larger IT problem I'm currently working on, I'm fairly helpless at the moment $\endgroup$ – Bogey Mar 4 '18 at 15:01
  • $\begingroup$ You can just simply count the number of ways, its very straightforward. $\endgroup$ – NewGuy Mar 4 '18 at 15:18
  • $\begingroup$ Hi @NewGuy, thanks - not quite sure I understand. Count as in, manually? In this example, sure; though I'm looking for a generalized solution that would work with an arbitrary number of groups $\endgroup$ – Bogey Mar 4 '18 at 15:22
2
$\begingroup$

I'll reword your question a bit. Let me know if I have not framed it properly.

Say we have a collection of $r$ unique elements each of which occurs in multiple copies. Namely, our collection has $n_1$ identical copies of $X_1$, $n_2$ identical copies of $X_2$, $\ldots$, and $n_r$ identical copies of $X_r$. How many ways can we form combinations of length $k$, where repeated copies of unique elements are allowed?

This question has a standard answer which can be derived informally and also formally (see below). In either case the answer is

$$ \sum_{\ell=0}^{r} (-1)^{\ell} \sum_{\textbf{j} \in \{n_k\}_{\ell} } \binom{k+r-1 - \sum_{i=1}^{\ell}(j_i +1)}{r-1} $$

where $\{n_k\}_{\ell}$ is the set of all $\ell$-length combinations of the elements $(n_1, \ldots, n_r)$, $\textbf{j} = (j_1, j_2, \ldots, j_{\ell})$ is a vector representing a particular element of the set of $\{n_k\}_{\ell}$, and the second summation is over all such combinations. (The $\ell=0$ term simply reduces to "$k+r-1$ choose $r-1$".)

We can apply the above formula to your example. In your case you have $r=3$ types of elements and you're trying to form combinations of length $k=4$. We identify the blue, orange, and yellow balls with $X_1$, $X_2$, and $X_3$ respectively. We then have $n_1 = 3$, $n_2 = 1$, and $n_3 =4$. The possible values of $\textbf{j}$ with defined by various $\ell$ are

\begin{eqnarray} \ell = 1: & \quad j_1 & \in \{3, 1, 4\} \\ \ell = 2: & \quad (j_1, j_2) & \in \{(3, 1), (1,4), (4, 3)\} \\ \ell = 3: & \quad (j_1, j_2, j_3) & \in \{(3, 1, 4) \} \end{eqnarray}

We thus find \begin{eqnarray} & & \binom{4+3-1}{3-1} - \Big[ \binom{4+3-1 -(3+1)}{3-1} +\binom{4+3-1 -(1+1)}{3-1}+\binom{4+3-1 -(4+1)}{3-1}\Big] \\ & & + \Big[ \binom{4+3-1 -(4+2)}{3-1} +\binom{4+3-1 -(5+2)}{3-1}+\binom{4+3-1 -(7+2)}{3-1}\Big]\\ & &- \Big[ \binom{4+3-1 -(8+3)}{3-1}\Big]\\ & = & \binom{6}{2} - \Big[\binom{2}{2} + \binom{4}{2}+ 0\Big] +\Big[0\Big] - 0 = 8, \end{eqnarray} where we used $\binom{n}{k} = 0$ if $n>k$. This result can be checked by listing the number of ways to form the elements.


Formal Derivation

To derive the general answer to the highlighted question, we note that the desired number is equal to the number of ways $\alpha_1$, $\alpha_2, \ldots, \alpha_r$ can all sum to $k$ where each $\alpha_k$ (i.e., the number of elements of $X_k$) runs from $0, 1, \ldots, n_k$. Namely, we want to compute $$ (\#)_{n_1,\ldots, n_r; k} = \sum_{\alpha_1=0}^{n_1}\cdots \sum_{\alpha_r=0}^{n_r} \delta_{k, \alpha_1+\cdots +\alpha_r}, $$ where $\delta_{\ell, m}$ is the Kronecker delta. To compute the above quantity, we need to use two identities both of which are established by the Cauchy's Integral Formula:

$$ \delta_{m, \ell} = \frac{1}{2\pi i} \oint_C \frac{dz}{z} z^{m-\ell}, \qquad \binom{k}{\ell} = \frac{1}{2\pi i} \oint_C dz\, \frac{z^{k}}{(z-1)^{\ell +1}}. $$ Using the contour integral representation of the Kronecker delta, we have

\begin{align} (\#)_{n_1,\ldots, n_r; k} & = \sum_{\alpha_1=0}^{n_1} \cdots \sum_{\alpha_{r}=0}^{n_r} \oint_C \frac{dz}{z} z^{k- \alpha_1- \cdots - \alpha_r}\\ & = \oint_C \frac{dz}{z} z^{k} \prod_{m=1}^{r} \sum_{\alpha_m=0}^{n_m} z^{-\alpha_k} \quad \text{[Commute summation and integral]} \\ & = \oint_C \frac{dz}{z} z^{k} \prod_{m=1}^{r} \frac{1-z^{-n_m-1}}{1-z^{-1}} \quad \text{[Geometric Series Identity]} \\ & = \oint_C dz \frac{z^{k+r-1}}{(z-1)^r} \prod_{m=1}^{r} \left(1- z^{-1} z^{-n_k}\right). \end{align}

Now, using the identity \begin{equation} \prod_{i=1}^N(1+\lambda x_i) = \sum_{\ell=0}^{N} \lambda^{\ell} \Pi_{\ell}(x_1, \ldots, x_N), \end{equation} where $\Pi_{\ell}(x_1, \ldots, x_N)$ is the $\ell$th elementary symmetric polynomial in the variables $(x_1, \ldots, x_N)$, we find \begin{align} (\#)_{n_1,\ldots, n_r; k} & = \sum_{\ell=0}^{r}(-1)^{\ell}\,\oint_C dz \frac{z^{k+r-1- \ell}}{(z-1)^r} \, \Pi_{\ell}(z^{-n_1}, \ldots, z^{-n_r}). \label{eq:omegpre} \end{align} For an arbitrary elementary symmetric polynomial we have the definition \begin{equation} \Pi_{\ell}(x_1, x_2, \ldots, x_r) = \sum_{ \textbf{j} \in \{1, 2, \ldots, r\}_{\ell} } x_{j_1} x_{j_2}\cdots x_{j_{\ell}}, \end{equation} where $\textbf{j} = (j_1, \ldots, j_{\ell})$ is a particular combination of length $\ell$ of the elements in $\{1, 2, \ldots, r\}$ and the summation is over all combinations of length $\ell$. For our case, we similarly have \begin{equation} \Pi_{\ell}(z^{-n_1}, \ldots, z^{-n_r}) = \sum_{ \textbf{j} \in \{n_k\}_{\ell} } z^{- j_1 - \ldots - j_{\ell}}. \end{equation} $(\#)_{n_1,\ldots, n_r; k} $ therefore becomes \begin{align} (\#)_{n_1,\ldots, n_r; k} & = \sum_{\ell=0}^{r}(-1)^{\ell}\, \sum_{ \textbf{j} \in \{n_m\}_{\ell} }\oint_C dz \, \frac{z^{k+r-1- \ell}}{(z-1)^r} \,z^{- j_1 - \ldots - j_{\ell}} \\ & = \sum_{\ell=0}^{r}(-1)^{\ell}\, \sum_{ \textbf{j} \in \{n_m\}_{\ell} }\oint_C dz\, \frac{z^{k+r-1- \sum_{i=1}^{\ell}(j_i +1)}}{(z-1)^r}. \end{align} Using the contour integral representation of the binomial, we ultimately find \begin{equation} (\#)_{n_1,\ldots, n_r; k} = \sum_{\ell=0}^{r}(-1)^{\ell}\, \sum_{ \textbf{j} \in \{n_m\}_{\ell} } \binom{k+r-1 - \sum_{i=1}^{\ell}(j_i +1)}{r-1}, \label{eq:omeggen} \end{equation} where $j_1, \ldots, j_{\ell}$ is a particular combination of $\ell$ elements in $\{n_1, \ldots, n_r\}$ and the second summation runs over all such combinations.


Some Special Cases

  1. For $n_k=1$ for all $k$, $\{n_1, \ldots, n_r\}$ becomes the $r$ element set $\{1, \ldots, 1\}$. Thus summing over all $\ell$-length combinations of $\{n_1, \ldots, n_r\}$ reduces to setting $j_i= 1$ for all $i$ and multiplying the relevant term by the number of ways to choose $\ell$ elements from a set of $r$ elements, i.e., $\binom{r}{\ell}$. We thus find \begin{equation} (\#)_{n_1,\ldots, n_r; k} = \sum_{\ell=0}^{r}(-1)^{\ell}\, \binom{r}{\ell} \binom{k+r-1 - 2\ell}{r-1}. \end{equation} However, if all $n_m$ are equal to 1, then the number of ways we can choose combinations of length $k$ from the elements $A_1, A_2, \ldots, A_r$ is simply the number of ways to choose $k$ elements from a set of $r$ elements. Thus we can conclude \begin{equation} \sum_{\ell=0}^{r}(-1)^{\ell}\, \binom{r}{\ell} \binom{k+r-1 - 2\ell}{r-1} = \binom{r}{k}. \end{equation}

  2. For $n_m = \infty$ for al $m$, then $j_i = \infty$ for all $i$ and all terms in \refew{omeggen} are zero except for $\ell=0$. (The binomial $\binom{n}{k}$ is zero whenever $n< k$). We thus have \begin{equation} (\#)_{n_1,\ldots, n_r; k} = \binom{k+r-1}{r-1}, \end{equation} which matches the standard result (see "Combination with repetitions." for example).

  3. For $n_m = n$ for all $m$, then $j_i = n$ for all $i$. Similar to the case in 1., summing over over all $\ell$-length combinations of $\{n_1, \ldots, n_r\}$ reduces to setting $j_i= n$ for all $i$ and multiplying the relevant term by the number of ways to choose $\ell$ elements from a set of $r$ elements. We therefore have \begin{equation} (\#)_{n_1,\ldots, n_r; k} = \sum_{\ell=0}^{r}(-1)^{\ell}\, \binom{r}{\ell} \binom{m+r-1 - \ell(n+1)}{r-1}, \end{equation} which matches the expression in the intuitive argument given by Thoma in "Basic inclusion exclusion problem - picking 24 balls out of four sets of 10 balls".

$\endgroup$
  • $\begingroup$ Wow, thanks for your extremely helpful and detailed answer! Very, very much appreciated! To note for others - I think this formula only works if there are more than 1 distinct groups. For example, if you only have 1 distinct group (that contains 6 items .. so r = 1, x_1 = 6 and k = 3) and you're trying to form groups consisting of 3 items, the formula would give 0, though the real result would be 1 $\endgroup$ – Bogey Mar 5 '18 at 10:14
  • $\begingroup$ Actually the formula would produce 1. You have to remember that $\binom{n}{k}=1$ if $k=0$ as long as $n\geq1$. Therefore, with $r=1$, $n_1=6$, and $k=3$, only the first term in the formula will survive and that term would yield $\binom{\text{"something"}}{r-1} = 1$. $\endgroup$ – Olukayode Mar 5 '18 at 15:10
  • 1
    $\begingroup$ Also, if possible, could you expand on the IT problem which motivates this question? Maybe include it in the problem prompt. (I'm curious because I originally considered this question based on statistical mechanics concerns.) $\endgroup$ – Olukayode Mar 5 '18 at 15:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.