2
$\begingroup$

We have to find the number of ways of distributing $5$ different balls to $4$ different persons.

Clearly, the answer is $4^5$ as each ball can be given to any of the $4$ persons. However, I wanted to calculate it using a different method.

I assumed that $a$ balls are given to first person, $b$ to second , $c$ to third and $d$ to fourth person. So we have that $a+b+c+d=5$ where $0 \leq a,b,c,d \leq 5$.

But counting the solutions to the above equation assumes that balls are identical. So I tried to find the number of distributions each permutation of $(a,b,c,d)$ produces. That will be $\displaystyle \binom{5}{a}\cdot \binom{5-a}{b}\cdot \binom{5-a-b}{c} $ which equals $\dfrac{5!}{a!b!c!d!}$.

So, now we need to sum this value over all $a,b,c,d$ satisfying $a+b+c+d=5$. Now there are $\displaystyle \binom{8}{3}=56$ solutions to the equation. So there will be $56$ terms in that summation. So how do we do that?

$\endgroup$
2
  • $\begingroup$ "I guess there should be an easy way of doing that"... no, not really. The first method is the preferred method here. Going down the tangent of trying to deal with stars-and-bars and then summing... while not inherently incorrect... is incredibly inefficient and does not easily simplify. $\endgroup$
    – JMoravitz
    Aug 27 '20 at 16:52
  • $\begingroup$ I see.... but I have seen problems involving these kinds of summations...for example the coefficients in a multinomial expansion are of this form....So I thought there might be a way.... So are you saying that there is no difficult way either? $\endgroup$ Aug 27 '20 at 16:54
3
$\begingroup$

Work backwards:

Suppose you already gave out $a$ balls to the first person and $b$ balls to the second. You now have $\binom{5-a-b}{c}$ ways of giving $c$ balls to the third person and the remaining balls to the fourth person. Summing this up for all possible value of $c$ gives: $\binom{5-a-b}{0}+\binom{5-a-b}{1}+...+\binom{5-a-b}{5-a-b}=2^{5-a-b}$.

Suppose you gave out $a$ balls to the first person. You now have $\binom{5-a}{b}$ ways of giving $b$ balls to the second person, and for each of those you are left with $2^{5-a-b}$ ways of giving out balls to the remaining two people. Summing this up for all values of $b$ gives: $\binom{5-a}{0}2^{5-a}+\binom{5-a}{1}2^{4-a}+...+\binom{5-a}{5-1}2^{0}=3^{5-a}$.

Lastly, summing for $a$, you have $\binom{5}{0}3^5+\binom{5}{1}3^4+\binom{5}{2}3^3+\binom{5}{3}3^2+\binom{5}{4}3^1+\binom{5}{5}3^0=4^5$.

This uses the identity: $$\sum_{k=0}^X\binom{X}{k}Y^k=\sum_{k=0}^X\binom{X}{X-k}Y^k=(Y+1)^X$$ This identity comes from the fact that this sum is what you get when you expand the binomial $(1+Y)^X$

$\endgroup$
3
$\begingroup$

Answering the question in the comments, about proving that for any $m\geq 1$ and $n\geq 0$: $$\sum_{x_1+x_2+...+x_m=n}\frac{1}{x_1!x_2!...x_m!}=\frac{m^n}{n!}$$

First, start by recognizing that $\sum_{k=0}^p\binom{p}{k}A^k=(A+1)^p$. If we expand the binomial expression, we get the sum.

Then prove by induction:

For $m=1$, the formula is trivially true.

For $m=2$:

$$\sum_{x_1+x_2=n}\frac{1}{x_1!x_2!}=\sum_{x_1=0}^n\frac{1}{x_1!(2-x_1)!} = \frac{1}{2!} \sum_{x_1=0}^n\frac{2!}{x_1!(2-x_1)!} = \frac{1}{2!} \sum_{x_1=0}^n\binom{n}{x_1} = \frac{2^n}{n!}$$

Given that it holds true for $1\leq m\leq s$, prove that it also holds true for $m=s+1$: $$\sum_{x_1+...+x_s+x_{s+1}=n}\frac{1}{x_1!...x_s!x_{s+1}!} = \sum_{x_{s+1}=0}^n\sum_{x_1+...+x_s=n-x_{s+1}=n}\frac{1}{x_1!...x_s!x_{s+1}!} = \sum_{x_{s+1}=0}^n\frac{1}{x_{s+1}!}\sum_{x_1+...+x_s=n-x_{s+1}=n}\frac{1}{x_1!...x_s!} = \sum_{x_{s+1}=0}^n\frac{1}{x_{s+1}!}\frac{s^{n-x_{s+1}}}{(n-x_{s+1})!} = \frac{1}{n!}\sum_{x_{s+1}=0}^n\frac{n!s^{n-x_{s+1}}}{(n-x_{s+1})!x_{s+1}!} =\frac{1}{n!}\sum_{x_{s+1}=0}^n\binom{n}{n-x_{s+1}}s^{n-x_{s+1}} = \frac{(s+1)^n}{n!}$$

$\endgroup$
1
  • $\begingroup$ Thank you so much! $\endgroup$ Aug 28 '20 at 3:56
2
$\begingroup$

Consider the partitions $5$ into $4$ parts \begin{eqnarray*} (5,0,0,0),(4,1,0,0),(3,2,0,0),(3,1,1,0),(2,2,1,0),(2,1,1,1). \end{eqnarray*} These have symmetry factors $4,12,12,12,12,4$ respectively (which adds upto $56$ as you state)

Now the balls can be distributed in each case and multiply in the symmetry factors ... \begin{eqnarray*} 4 \times \frac{5!}{5!0!0!0!} + 12 \times \dfrac{5!}{4!1!0!0!} + 12 \times \dfrac{5!}{3!2!0!0!} + 12 \times \dfrac{5!}{3!1!1!0!} + 12 \times \dfrac{5!}{2!2!1!0!} + 4 \times \dfrac{5!}{2!1!1!1!} =1024= 4^5. \end{eqnarray*}

$\endgroup$
4
  • $\begingroup$ That works for me, but can you tell me if there's a formula for the sum $$\sum_{a+b+c=n} \frac{1}{a!b!c!}$$ $\endgroup$ Aug 27 '20 at 17:19
  • $\begingroup$ @ABCD: That isn't quite the sum that comes up in the problem, but $\sum_{x_1+x_2+...+x_m=n}\frac{1}{x_1!x_2!...x_m!}=\frac{m^n}{n!}$. In what you just asked, $m=3$ and the sum is $\frac{3^n}{n!}$ $\endgroup$
    – Moko19
    Aug 27 '20 at 17:39
  • $\begingroup$ @Moko19, I know that sum doesn't come up in the problem, I was just wondering how to evaluate that sum. Can I have a link of a proof for this? I would first try to prove it myself, then If I failed, then I would look it up...thanks for the answering though! $\endgroup$ Aug 27 '20 at 18:17
  • $\begingroup$ @ABCD: I started giving a proof in the comments, but it got too long and unmanageable. I'll give it as an alternate answer to the question, in addition to my original answer that begins "Work Backwards" $\endgroup$
    – Moko19
    Aug 27 '20 at 21:06

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.