7
$\begingroup$

In how many ways can you distribute 4 distinct balls between 3 people such that none of them gets exactly 2 balls?

This is what I did (by the inclusion–exclusion principle) and I'm not sure, would appreciate your feedback: $$3^4-\binom{3}{1}\binom{4}{2}\binom{2}{1}^2+\binom{3}{2}\binom{4}{2}\binom{2}{1}$$

$\endgroup$
7
$\begingroup$

Method 1: If no person receives exactly two balls, there are two possible cases. One person receives all four balls or one person receives three balls and another person receives one ball.

Case 1: One person receives all four balls.

There are three ways of selecting the person who receives all the balls.

Case 2: There are three ways of selecting the person who receives three balls, $\binom{4}{3}$ ways of selecting which three of the four balls that person receives, and two ways of choosing the person who receives the remaining ball. Consequently, there are $$\binom{3}{1}\binom{4}{3}\binom{2}{1}$$ of distributing three of the balls to one person and one ball to another person.

Note that Parcly Taxel and Jon Mark Perry obtained the factor of $$3! = \binom{3}{1}\binom{2}{1}$$ in this case by making the observation that there are $3!$ ways of distributing different numbers of balls to three different people.

Total: Since these cases are disjoint, the number of ways of distributing four distinct balls to three people so that no person receives exactly two balls is $$\binom{3}{1} + \binom{3}{1}\binom{4}{3}\binom{2}{1}$$

Method 2: Exclude those cases in which one person receives exactly two balls from the total.

Since both the people and the balls are distinct, there would be $3^4$ ways of distributing the balls to the people if there were no restrictions.

There are two cases in which a person receives exactly two balls. Either one person receives two balls, while the others receive one each, or two people receive two balls each.

Case 1: One person receives two balls, while the others receive one each.

There are three ways to select the person who receives two balls, $\binom{4}{2}$ ways of selecting the balls that person receives, two ways of selecting a ball for the remaining person whose name appears first alphabetically, and one way to give the remaining person the remaining ball. $$\binom{3}{1}\binom{4}{2}\binom{2}{1}\binom{1}{1}$$

Case 2: Two people each receive two balls.

There are $\binom{3}{2}$ ways to select which two people receive two balls, $\binom{4}{2}$ ways to choose which two balls are given to the selected person whose name appears first alphabetically, and one way to give the remaining two balls to the other selected person. $$\binom{3}{2}\binom{4}{2}\binom{2}{2}$$

Total: Since the cases are disjoint, the number of ways of distributing four distinct balls to three people so that no person receives exactly two balls is $$3^4 - \binom{3}{1}\binom{4}{2}\binom{2}{1} - \binom{3}{2}\binom{4}{2}$$

Method 3: We use the Inclusion-Exclusion Principle.

There are $3^4$ ways of distributing four distinct balls to three people.

We must exclude those cases in which a person receives exactly two balls.

There are three ways of selecting a person to receive exactly two balls, $\binom{4}{2}$ ways of choosing which balls that person receives, and $2^2$ ways of distributing the remaining two balls to the other people. Hence, there are $$\binom{3}{1}\binom{4}{2}2^2$$ ways of distributing the balls so that a person receives exactly two of them.

However, we have counted those distributions in which two people receive two balls each twice, once for each of the people we designated as the person who receives two balls. In Method 2, we calculated that the number of distributions in which two people each receive two balls is $$\binom{3}{2}\binom{4}{2}$$

Hence, by the Inclusion-Exclusion Principle, the number of ways of distributing four distinct balls to three people so that no person receives exactly two balls is $$3^4 - \binom{3}{1}\binom{4}{2}2^2 + \binom{3}{2}\binom{4}{2}$$ You calculated the last term incorrectly.

$\endgroup$
5
$\begingroup$

Note that the only partitions of 4 into 3 parts avoiding 2 are $(0,1,3)$ and $(0,0,4)$.

  • For the first case, there are $3!=6$ ways of distributing these numbers of balls to the three people and 4 choices for the ball given to the person with one ball, at which point the distribution is complete. This yields 24 possible distributions.
  • The second case simply has 3 ways to select the person getting all the balls.

Hence there are 27 ways given the constraints, which does not match your answer of 45.

$\endgroup$
3
$\begingroup$

One person gets $4$ balls: $3$ ways

One person gets $3$ balls, one person gets $1$: $\dbinom41\times3!=24$

$27$ in total.

$\endgroup$
  • $\begingroup$ +1. Straightforward and quite simple answers. I was puzzled for awhile because I didn't notice the $\underline{distinct}$ condition. That is why we have the $3!$. $\endgroup$ – Felix Marin Sep 16 '16 at 4:15
1
$\begingroup$

Here is a variation based upon generating functions. Distributing $0$ up to $4$ distinguishable balls to three persons can be represented by \begin{align*} \left(1+t+\frac{1}{2!}t^2+\frac{1}{3!}t^3+\frac{1}{4!}t^4\right)^3\tag{1} \end{align*}

The coefficient of $t^4$ multiplied with $4!=24$ in the expanded expression of (1) gives the number of possibilities to distribute four balls to three persons.

Since we do not want that a person gets precisely two balls we use a marker $x$ to indicate this event.

\begin{align*} \left(1+t+\color{blue}{x}\cdot \frac{1}{2}t^2+\frac{1}{6}t^3+\frac{1}{24}t^4\right)^3\tag{2} \end{align*}

We use the coefficient of operator $[t^j]$ to denote the coefficient of $t^j$ in a series and have to calculate $[t^4x^0]$ in (2).

We obtain \begin{align*} 4!\cdot[t^4x^0]&\left(1+t+x\cdot\frac{1}{2}t^2+\frac{1}{6}t^3+\frac{1}{24}t^4\right)^3\\ &=4!\cdot[t^4x^0]\left(1+3t+\frac{1}{2}t^2(3x+6)+\frac{1}{6}t^3(18x+9) +\frac{1}{24}t^4(18x^2+36x+27)\right)\\ &=4!\cdot[x^0]\left(\frac{1}{24}(18x^2+36x+27)\right)\\ &=27 \end{align*}

We observe out of $18+36+27=81$ possibilities to distribute four distinghishable balls to three persons there are

$\qquad\color{blue}{27} $ possibilities so that none of them has two balls

$\qquad36 $ possibilities so that exactly one of them has two balls and

$\qquad18 $ possibilities so that two of them have two balls.

Comment:

  • In the second line we expand only up to powers of $t^4$ since higher powers do not contribute anything to $[t^4]$. We select the coefficient of $t^4$.

  • In the following line we select the coefficient of $x^0$.

$\endgroup$

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.