5
$\begingroup$

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) -

  1. Person one gets 9 red a 1 blue ball and person two gets 10 red balls.
  2. 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 -

  1. RRR / RBY
  2. RBY / RRR
  3. RRB / RRY
  4. 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.

$\endgroup$
1
  • 3
    $\begingroup$ You could try a generating function approach: if there are $2n=W+X+Y+\cdots+k$ balls in total, you want the coefficient of $x^n$ in the expansion of $(1+x+x^2+\cdots+x^W)(1+x+x^2+\cdots+x^X)(1+x+x^2+\cdots+x^Y)\cdots(1+x+x^2+\cdots+x^k)$. You can rewrite this as $\frac{1-x^{W+1}}{1-x}\frac{1-x^{X+1}}{1-x}\frac{1-x^{Y+1}}{1-x}\cdots\frac{1-x^{k+1}}{1-x}$ $\endgroup$
    – Henry
    Feb 23, 2021 at 16:08

1 Answer 1

1
$\begingroup$

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. $$

$\endgroup$
3
  • $\begingroup$ Thank you for this! Would you mind showing how this formula would work on an example, please? Lets take "Example 4" from the original question - assume I have 4 red balls (R) and 1 blue ball (B) and 1 yellow ball (Y) - how does this formula produce 4 as an answer? $\endgroup$
    – Yuriy
    Mar 4, 2021 at 14:58
  • $\begingroup$ @Yuriy I have included the required example. Hope you enjoy it. $\endgroup$
    – user
    Mar 4, 2021 at 17:09
  • 1
    $\begingroup$ Got it, thank you! $\endgroup$
    – Yuriy
    Mar 4, 2021 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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