1
$\begingroup$

Find Number of ways to distribute $4$ identical red balls , $4$ identical green balls, $4$ identical white balls, $4$ identical black balls among four people so that each person receives at least one ball but no one gets $4$ red balls.

There is a really similar question here ; Number of ways of distributing $4$ identical red balls,$1$ green ball,$1$ black ball among $4$ persons . But in my book, it was written : Number of ways of distributing $4$ identical red, green, black, white balls among $4$ persons so that each person receives at least one ball but no one gets $4$ red balls.

So i interpreted the question as the question i am posting now and i just couldn't solve it. So i looked it up on MSE and found the question (link attached). So i am wondering if it is even possible to solve that question because I can not stop thinking about it but i just can't solve it.

Thanks!

I THINK THIS PROBLEM IS WRONG

$\endgroup$
13
  • $\begingroup$ I started to compose an answer, but had to discard it, because I couldn't find an elegant way of managing the constraints. Without knowing anything about generating functions, let alone exponential generating functions, I can't help but wonder if this problem requires exponential generating functions. $\endgroup$ Dec 12 '20 at 11:12
  • $\begingroup$ @user2661923 if you can give a solution with generating functions, that would be good too because i am about to start learning them anyway. $\endgroup$ Dec 12 '20 at 16:03
  • $\begingroup$ What have you tried? Where are you stuck? $\endgroup$ Dec 12 '20 at 16:07
  • $\begingroup$ First of all, I don't even know if generating functions &/or exponential generating functions will solve the problem. What I do know is that I can't solve the problem any other way (maybe someone else can). Also, I haven't studied any type of generating functions, so I can't even try such an approach. $\endgroup$ Dec 12 '20 at 18:26
  • $\begingroup$ @N.F.Taussig I can tell you where I am stuck. I am able to use Stars and Bars, considering the distribution of each of the 4 colors independently. Further, I am able to elegantly adjust (still within Stars and Bars) for no person being allowed to get all 4 red balls. However, I can not find anyway to elegantly (re Inclusion-Exclusion) adjust for each person also being required to get at least one ball. Attempting (for example) $x_1 + x_2 + x_3 + x_4 = [16]$ or $x_1 + x_2 + x_3 + x_4 = [16-4]$ ignores that the colors are distinct. ...see next comment $\endgroup$ Dec 12 '20 at 18:32
3
$\begingroup$

Begin by distributing the green, white, and black balls arbitrarily. Let $A_k$ be the set of distributions where exactly $k\in[4]$ persons get $\geq1$ balls. The $|A_k|$ can be calculated by distributing arbitrarily to $4$, $3$,$2$, $1$ persons and using inclusion exclusion. E.g., there are ${7\choose3}^3$ arbitrary distributions to $4$ persons, then ${6\choose2}^3$ arbitrary distributions to $3$ persons, etcetera.

For each $k\in[4]$ compute the number $n_k$ of ways to finally distribute the $4$ red balls such that in all an admissible distribution results. E.g., when $k=3$, give the person $P$ having no ball yet a red ball, and distribute the remaining three red balls arbitrarily among the $4$ persons, except all three of them to $P$. The final number $N$ then is $$N=\sum_{k=1}^4 n_k\,|A_k|\ .$$

$\endgroup$
4
  • $\begingroup$ @trueblueanil: We see a certain distribution of all other balls. Maybe it is in $A_3$, and person $P_2$ has no ball. Then $P_2$ gets one red ball. We then distribute the three other red balls arbitrarily, but not all of them to $P_2$. The number $n_3$ depends only on "$3$", and not on the name "$2$" of the person. $\endgroup$ Dec 13 '20 at 14:50
  • $\begingroup$ By symmetry, for $A_3$, say, won't there be four configurations where one person has no ball ? In other words, it is enough to know that exactly one or two or three persons have no ball ? Nice answer (+1) $\endgroup$ Dec 14 '20 at 12:58
  • $\begingroup$ @trueblueanil: There are $4$ distributions where $1$ person has all green, white and black (=: gwb) balls. The set $A_3$ consists of all gwb distributions where $3$ persons have some gwb balls and $1$ person has no gwb ball. This set is very large, but all distributions in $A_3$ can be supplemented in $n_3$ ways with red balls so that an admissible full distribution results. $\endgroup$ Dec 14 '20 at 13:13
  • $\begingroup$ It is not clear to me how to apply inclusion-exclusion here. Consider $9$ balls, $3$ each of $3$ different colors to be give to $3$ people. Leaving out the red balls, with the rest of one color, I would compute total configurations as $\binom8 2 = 28$, and exactl one person not getting as $\binom31\cdot\binom71 - 2\times\binom32 \binom6 0 = 15$, but when I consider balls of two colors, there are $\binom5 2 ^2 = 100$ configurations of which $42$ have exactly one person not getting any. How do i apply inclusion-exclusion here ? $\endgroup$ Dec 15 '20 at 8:58
1
$\begingroup$

Note [2020-12-25]: This is a completely revised answer.


This answer consists of three parts. In the first part we give a solution to the problem. The second part is a generalisation which can be derived easily and we find a nice identity of Stirling numbers of the second kind. In the third part we calculate a small example by hand as plausibility check.

A solution: This solution is based upon PIE, the principle of inclusion-exclusion.

  • The number of ways to distribute four identical balls to four persons so that each of them has zero or more balls is using stars and bars \begin{align*} \binom{4+4-1}{4-1}=\binom{7}{3}\tag{1} \end{align*} We start with a formula for distributing zero or more balls and not at least one ball, since balls with other colors will also be used for distribution to the people.

  • We have four different colors with four balls each. The number of ways to distribute these balls, so that each of the persons has zero or more balls is according to (1) \begin{align*} \binom{7}{3}^4\tag{2} \end{align*}

  • Now we subtract from (2) according to PIE, the principle of inclusion-exclusion, the cases where at least one of the four persons has no ball. Since one person can be selected in $\binom{4}{1}$ ways, we get as number to subtract \begin{align*} \binom{4}{1}\binom{4+3-1}{3-1}=\binom{4}{1}\binom{6}{2} \end{align*} But here we did some overcounting, since we counted the cases where two of the four persons has no ball, twice. To compensate this we add $\binom{4}{2}$ times the number of ways to distribute the balls to two persons and so on. We obtain this way \begin{align*} \sum_{i=0}^3(-1)^i\binom{4}{i}\binom{7-i}{3-i}^4\tag{3} \end{align*}

  • Finally we have to respect that four red balls are not allowed to be distributed to one person only. In order to do so we calculate the number of ways to distribute three times four balls of the other colors to four persons. Since we have $\binom{4}{1}$ ways to give the four red balls to a person we have to subtract: \begin{align*} \binom{4}{1}\sum_{i=0}^3(-1)^i\binom{4}{i}\binom{7-i}{3-i}^3\tag{4} \end{align*} One final aspect we missed so far is that we additionally have to subtract the $\binom{4}{1}=4$ cases where four red balls are given to a person and this person has no other balls. These $4$ cases also have to be subtracted.

We obtain from (3) and (4) the number of wanted ways as \begin{align*} &\color{blue}{\sum_{i=0}^3(-1)^i\binom{4}{i}\binom{7-i}{3-i}^4-\binom{4}{1}\sum_{i=0}^3(-1)^i\binom{4}{i}\binom{7-i}{3-i}^3-\binom{4}{1}}\\ &\quad=\left[\binom{4}{0}\binom{7}{3}^4-\binom{4}{1}\binom{6}{2}^4+\binom{4}{2}\binom{5}{1}^4-\binom{4}{3}\binom{4}{0}^4\right]\\ &\quad\quad-\binom{4}{1}\left[\binom{4}{0}\binom{7}{3}^3-\binom{4}{1}\binom{6}{2}^3 +\binom{4}{2}\binom{5}{1}^3-\binom{4}{3}\binom{4}{0}^3\right]-\binom{4}{1}\\ &\quad=\left[1\cdot1\,500\,625-4\cdot50\,625+6\cdot625-4\cdot1\right]\\ &\quad\quad-4\left[1\cdot 42\,875-4\cdot 3\,375+6\cdot125-4\cdot1\right]-4\\ &\quad=1\,301\,871-120\,484-4\\ &\,\,\quad\color{blue}{=1\,181\,383}\tag{5} \end{align*}

A generalisation:

  • We can easily derive the following generalisation of (3) from the approach above: We consider $n$ pairwise distinct colors $C_1, C_2, \ldots, C_n$ and $b_1+b_2+\cdots+b_n$ balls where $b_j$ balls have color $C_j, 1\leq j\leq n$. The number of ways to distribute $b_1+\cdots+b_n$ balls to $k$ persons is \begin{align*} \color{blue}{\sum_{i=0}^{k-1}(-1)^i\binom{k}{i}\prod_{j=1}^n\binom{b_j+k-i-1}{k-i-1}}\tag{6} \end{align*}

  • We consider the special case $b_1=b_2=\cdots=b_n=1$. Here we have $n$ different(ly colored) balls and we can reformulate the wanted number as $k!$ times the number of ways to partition $n$ numbers into $k$ sets. This is ${n \brace k}k!$, with $n\brace k$ the well-known Stirling numbers of the second kind.

We derive from (6) the identity \begin{align*} \color{blue}{{n\brace k}k!}&=\sum_{i=0}^{k-1}(-1)^i\binom{k}{i}\prod_{j=1}^n\binom{1+k-i-1}{k-i-1}\\ &=\sum_{i=0}^{k-1}(-1)^i\binom{k}{i}\binom{k-i}{k-i-1}^n\\ &\,\,\color{blue}{=\sum_{i=0}^{k-1}(-1)^i\binom{k}{i}(k-i)^n}\\ \end{align*}

An example:

Here we consider as application and plausibility check of the formulas (5) and (6) the following problem.

  • Find the number of ways to distribute $2$ identical red balls , $2$ identical green balls, $2$ identical white balls among two people so that each person receives at least one ball but no one gets $2$ red balls.

We have the situation $n=3, b_1=b_2=b_3=2$ and we have two persons, which means $k=2$. The wanted number is following (5) and (6)

\begin{align*} &\sum_{i=0}^{2-1}(-1)^i\binom{2}{i}\binom{2+2-i-1}{2-i-1}^3\\ &\qquad-\binom{2}{1}\sum_{i=0}^{2-1}(-1)^i\binom{2}{i}\binom{2+2-i-1}{2-i-1}^2-2\\ &=\sum_{i=0}^{1}(-1)^i\binom{2}{i}\binom{3-i}{1-i}^3 -2\sum_{i=0}^{1}(-1)^i\binom{2}{i}\binom{3-i}{1-i}^2-2\\ &=\left[\binom{2}{0}\binom{3}{1}^3-\binom{2}{1}\binom{2}{0}^3\right] -2\left[\binom{2}{0}\binom{3}{1}^2-\binom{2}{1}\binom{2}{0}^2\right]-2\\ &=25-2\cdot7-2\\ &\,\,\color{blue}{=9} \end{align*}

We list all $25$ cases, give the $9$ valid cases in boldface and mark the $2\cdot7$ and $2$ cases which are not valid blue and red. We have \begin{align*} \begin{array}{cccccc} \mathbb{g|g\color{blue}{rr}ww}&\mathbb{gg|\color{blue}{rr}ww}&\mathbf{ggr|rww}&\mathbb{gg\color{blue}{rr}|ww}&\mathbb{gg\color{blue}{rr}w|w}&\mathbf{ggrw|rw}\\ \mathbf{ggrww|r}&\mathbb{ggw|\color{blue}{rr}w}&\mathbb{ggww|\color{red}{rr}}&\mathbf{ggr|grww}&\mathbb{g\color{blue}{rr}|gww}&\mathbb{g\color{blue}{rr}w|gw}\\ \mathbb{g\color{blue}{rr}ww|g}&\mathbf{grw|grw}&\mathbf{grww|gr}&\mathbb{gw|g\color{blue}{rr}w}&\mathbb{gww|g\color{blue}{rr}}&\mathbf{r|ggrww}\\ \mathbb{\color{red}{rr}|ggww}&\mathbb{\color{blue}{rr}w|ggw}&\mathbb{\color{blue}{rr}ww|gg}&\mathbf{rw|ggrw}&\mathbf{rww|ggr}&\mathbb{w|gg\color{blue}{rr}w}\\ \mathbb{ww|gg\color{blue}{rr}}&&&&& \end{array} \end{align*}

$\endgroup$
5
  • $\begingroup$ thank you for such a nice and detailed answer, I really appreciate the effort you put into this. $\endgroup$ Dec 13 '20 at 21:26
  • 1
    $\begingroup$ Maybe I'm not understanding. If 3 identical balls are distributed to 3 people, we get $\binom{3+3-1}{3-1} = 10$ configurations. If there are three colors, there can be ${10}^3 = 1000$ configurations without any constraints. So how are you getting such a large number ? $\endgroup$ Dec 14 '20 at 14:18
  • 1
    $\begingroup$ @MarkusScheuer ok! $\endgroup$ Dec 14 '20 at 15:05
  • $\begingroup$ I think you should let it remain with a remark that the solution addresses a different (more complicated !) problem, it is an interesting answer. You can always post a solution to the simpler problem whenever you want. $\endgroup$ Dec 14 '20 at 15:06
  • $\begingroup$ @Aditya_math: I've revised my answer. Regards, $\endgroup$
    – epi163sqrt
    Dec 25 '20 at 10:32

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.