1
$\begingroup$

I have found a (In how many ways can 4 red balls and 7 blue balls be arranged in 3 boxes)(question).

The question says:

In how many ways can 4 red balls and 7 blue balls be arranged in 3 boxes where each box must contain at least 1 red ball and each box can contain less than or equal or 4 balls, under the following cases?

(1) Each ball is distinct and Each box is distinct

(2) Each ball is distinct and Each box is identical

For the first part I have come up with two distinct solutions:

First solution:

Distribute the red balls such that select which box will have two red balls and distribute others: $$\binom{4}{2}\times 3 \times 2$$

Now we have 7 distinct balls to distribute. The box containing two red balls can have at most two balls, and the other box can have maximum three balls. Then use exponential generating functions to disperse them: $$7! \times [x^7]\bigg(1+x+\frac{x^2}{2!}\bigg)\bigg(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\bigg)^2$$ $$36 \times \frac{7!}{9}=20160$$

Second way: Give one red ball to each boxes such that $$4 \times 3 \times 2 =24$$

Now, we have $8$ distinct ball to be distributed where each box can contain at most $3$ ball now. So $$8![x^8]\bigg(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\bigg)^3$$ $$24 \times \frac{8!}{24}=40320$$

Which answer is correct ? There are some other solutions in given links. PLease explain if my answers is wrong.

NOTE: For the second part , I thought dividing the result by $3!$

$\endgroup$

2 Answers 2

1
$\begingroup$

In how many ways can $4$ red balls and $7$ blue balls be arranged in $3$ boxes where each box must contain at least $1$ red ball and each box can contain less than or equal or $4$ balls if each ball is distinct and each box is distinct?

Your first solution is correct. We can confirm this by direct calculation.

In what follows, assume that the red balls are numbered from 1 to 4 and that the seven blue balls are numbered from 1 to 7.

The red balls must be distributed so that one box receives two red balls and each of the other boxes receives one red ball. There are three ways to select the box that receives two balls, $\binom{4}{2}$ ways to select which two red balls are placed in that box, and $2!$ ways to distribute the remaining two red balls to the remaining two boxes so that each of those boxes receives one red ball. Hence, there are $$\binom{3}{1}\binom{4}{2}2!$$ ways to distribute the red balls.

The restriction that each box can receive at most four balls leaves two possible distributions of numbers of blue balls:

  • One blue ball is placed in the box with two red balls and three red balls each are placed in the boxes with one red ball.
  • Two blue balls are placed in the box with two red balls, three red balls are placed in one of the boxes with one red ball, and the other two blue balls are placed in the other box with one red ball.

One blue ball is placed in the box with two red balls and three red balls each are placed in the boxes with one red ball: There are seven ways to select the blue ball that will be placed in the box with two red balls and $\binom{6}{3}$ ways to select which three of the remaining six blue balls will be placed in the box with the lower-numbered of the two red balls that are in the two boxes which each contain one red ball. The other three blue balls must be placed in the remaining box with one red ball. Hence, there are $$\binom{7}{1}\binom{6}{3}$$ such distributions.

Two blue balls are placed in the box with two red balls, three red balls are placed in one of the boxes with one red ball, and the other two blue balls are placed in the other box with one red ball: There are $\binom{7}{2}$ ways to select which two blue balls will be placed in the box with two red balls, $\binom{2}{1}$ ways to select which of the two boxes containing one red ball will receive three blue balls, and $\binom{5}{3}$ ways to select which three of the remaining five blue balls will be placed in that box. The remaining box with one red ball must receive the other two blue balls. Hence, there are $$\binom{7}{2}\binom{2}{1}\binom{5}{3}$$ such distributions.

Hence, there are $$\binom{3}{1}\binom{4}{2}2!\left[\binom{7}{1}\binom{6}{3} + \binom{7}{2}\binom{2}{1}\binom{5}{3}\right] = 20,160$$ ways to distribute four distinct red balls and $7$ distinct blue balls to three distinct boxes so that each box receives at least one red ball and no box receives more than four balls in total.

In your second attempt, by designating one of the two red balls in the box with two red balls as the red ball in that box and the other as the additional ball, you counted each distribution twice, once for each way you could have designated one of the two red balls in that box as the red ball in that box. To illustrate, suppose that you place red ball 1 in box 1, red ball 2 in box 2, and red balls 3 and 4 in box 3. Your second approach counts this distribution twice:

$$ \begin{array}{c c c c} \text{red ball in box 1} & \text{red ball in box 2} & \text{red ball in box 3} & \text{additional red ball in box 3}\\ \hline 1 & 2 & 3 & 4\\ 1 & 2 & 4 & 3 \end{array} $$

In how many ways can $4$ red balls and $7$ blue balls be arranged in $3$ boxes where each box must contain at least $1$ red ball and each box can contain less than or equal or $4$ balls if each ball is distinct but the boxes are indistinguishable?

Yes, you can obtain the answer by dividing your answer to the first part by the $3!$ ways of labeling the three boxes.

To see this, consider the distribution of the red balls. We must choose which two of the four red balls are placed in the same box, which can be done in $\binom{4}{2}$ ways. That leaves us with two distinct red balls and two empty boxes. Distribute those two red balls so that one is placed in each of the empty boxes. Since those boxes are indistinguishable, it does not matter which of the three boxes receives two red balls, nor does it matter which of the two remaining boxes receives which of the two remaining red balls. Hence, there are $$S(4, 3) = \binom{4}{2} = \frac{1}{3!} \cdot \binom{3}{1}\binom{4}{2}2!$$ ways to distribute four distinct red balls to three indistinguishable boxes so that no box is left empty, where $S(n, k)$ is a Stirling number of the second kind, the number of ways of distributing $n$ distinct balls to $k$ indistinguishable boxes when no box is left empty.

Once we have placed the red balls, the three boxes are distinguished by their contents. Thus, we may treat them as distinct when distributing the blue balls.

Hence, the number of ways of distributing four red balls and seven blue balls to three indistinguishable boxes so that each box receives at least one red ball and no box receives more than four balls in total is $$\binom{4}{2}\left[\binom{7}{1}\binom{6}{3} + \binom{7}{2}\binom{2}{1}\binom{5}{3}\right] = \frac{1}{3!} \cdot \binom{3}{1}\binom{4}{2}2!\left[\binom{7}{1}\binom{6}{3} + \binom{7}{2}\binom{2}{1}\binom{5}{3}\right] = 3360$$

$\endgroup$
0
$\begingroup$

$Q1$

1: Your first answer is correct.

[2]: Your second answer overcounts, (in fact exactly double counts) because you have put one red ball in each box first. For the double red box, R1 initially and R3 later is the same as putting R3 first and R1 later

$Q2$

For the second part, there is a subtlety, we can't straight away divide by $3!$ . As requested, I am giving a non-G.F. answer to clarify.


Non-G.F. answer

There are two possible configurations

$2R\;1B\;\;1R\;3B\;\;1R\;3B$, with $3$ permutations, and
$2R\;2B\;\;1R\;2B\;\;1R\;3B$, with $6$ permutations.

So for part $1$, the computation is

$3\times\binom42\binom71\binom21\binom63 + 6\times\binom42\binom72\binom21\binom52 = 20160$

while for part $2$, the computation is $\;\;\binom42\binom71\binom21\binom63\div 2! + \binom42\binom72\binom21\binom52 = 3360$

You could have a look here on team formation

$\endgroup$
11
  • $\begingroup$ what about the answers in given original question $\endgroup$
    – user1247042
    Commented Nov 6, 2023 at 7:24
  • $\begingroup$ At a cursory glance, the two answers posted don't match, sometimes (in answers or comments) a formula is written but results don't match, etc. If you want an answer by a non-g.f. approach, you should post a separate question. $\endgroup$ Commented Nov 6, 2023 at 7:47
  • $\begingroup$ you may write your own answer without using g.f, I can accept it. However, when I calculate the result given by @Kemp, does not comply with mine. It is $5040$. $\endgroup$
    – user1247042
    Commented Nov 6, 2023 at 8:01
  • $\begingroup$ I guess you made mistake in part 2, because the answer according to g.f. is 3360. The former expression must be divided by $2$ $\endgroup$
    – user1247042
    Commented Nov 6, 2023 at 10:06
  • $\begingroup$ divided by $2$ after multiplying by $\; 3!=6$ $\endgroup$ Commented Nov 6, 2023 at 10:15

You must log in to answer this question.