Given an even number of balls of different colours, find the number of ways of splitting these balls evenly between two people. The total number of balls is known, it is always even (and therefore could always be split evenly between two people), but may be large. Each ball has a colour. The colours and the quantities of each colour are known in advance, but there could be many colours. The order of the picking doesn't matter – all balls of the same colour are the same. Here are a few examples:
Example 1:
Given 2 red balls, how many ways there are to split them?
Answer: Well, just 1 – each person gets one red ball.
Example 2:
Given 20 red balls, how many ways there are to split them?
Answer: Still just 1 – each person gets 10 red balls.
Example 3:
Given 19 red balls and 1 blue ball, how many ways there are to split them?
Answer: Two ways (in fact, it doesn't matter how many red balls there are in this example, it will always be two ways) –
- Person one gets 9 red a 1 blue ball and person two gets 10 red balls.
- Person two gets 9 red a 1 blue ball and person one gets 10 red balls.
Example 4:
Given 4 red balls (R) and 1 blue ball (B) and 1 yellow ball (Y), how many ways there are to split them?
Answer: Four ways –
- RRR / RBY
- RBY / RRR
- RRB / RRY
- RRY / RRB
You get the idea. Now, in the general case, given W blue balls, X green balls, Y red balls, Z brown balls, … $k$ balls of colour C, how many ways are there to split them evenly between two people? Is there a generic formula that can be applied?
I have been at it for days, but short of counting all possible permutations by hand, I cannot really see a pattern that can be generalised.
Best Answer
Let the number of colors be $k$, the number of balls $2n$, and the number of balls of the $i$-th color be $r_i$, so that $\sum_{i=1}^k r_i=2n$
In terms of generating functions we are looking for the coefficient at $x^n$ in the product: $$\begin{align} \prod_{i=1}^k\sum_{j=0}^{r_i}x^j &=\prod_{i=1}^k\frac{1-x^{r_i+1}}{1-x}\\ &=\frac{\prod_{i=1}^k(1-x^{r_i+1})}{(1-x)^{k}}\\ &=\prod_{i=1}^k(1-x^{r_i+1})\sum_{j=0}^\infty\binom{-k}{j}(-x)^j\\ &=\prod_{i=1}^k(1-x^{r_i+1})\sum_{j=0}^\infty\binom{j+k-1}{j}x^{j}\\ &=\sum_{\boldsymbol{\mu}}(-1)^{|\boldsymbol{\mu}|}x^{\boldsymbol{\mu}\cdot\boldsymbol{r}} \sum_{j=0}^\infty\binom{j+k-1}{k-1}x^{j}, \end{align}$$ which is $$ \sum_{\boldsymbol{\mu}}(-1)^{|\boldsymbol{\mu}|}\binom{n-\boldsymbol{\mu}\cdot\boldsymbol{r}+k-1}{k-1},\tag1 $$ where $\boldsymbol{\mu}$ are all $2^k$ binary vectors of the length $k$, $|\boldsymbol{\mu}|=\sum_{i=1}^k\mu_i$ and $\boldsymbol{r}=(r_1+1,r_2+1,\dots,r_k+1)$.
In (1) the binomial coefficient $\binom mn$ is assumed to be $0$ for $m<n$.
Solution for Example 4.
$n=3,k=3,\boldsymbol{r}=(5,2,2):$
$$\binom 52-\binom 32-\binom 32=10-3-3=4. $$