In how many ways can 20212022 identical balls be arranged in 2022 different bins [with conditions]?

61 Views Asked by At

The problem goes like this: in how many ways can 20212022 identical balls be arranged in 2022 different bins so that the number of bins with exactly 4 balls is 3, with exactly 7 balls is 4 (2), and the remaining bin have at least 19 balls each (1)? I've attempted to approach it thus:

(1)

Let there be a vector $A=(x_{1}, x_{2}, ..., x_{2022})$, where $x_{i}$ is a positive integer and represents amount of balls in a bag $i$: $x_{1}+x_{2}+ ... +x_{2022}=20212022$

We can arrange $20212022-4*3-7*4 = 20211982$ balls in $2022-3-4=2015$ bins (ignoring those $4*3+7*4$ balls for 7 bins with fixed amounts of balls) by building a bijection between $A_{1}=(x_{1}, x_{2}, ..., x_{2015})$ and $B=(y_{1}+19, y_{2}+19, ..., y_{2015}+19)$, where $x_{i}=y_{i}+19$.

Then $y_{1}+y_{2}+ ... +y_{2015}=20211982-2015*19=20173697$. \begin{equation} \binom{n-1+k}{k}=\binom{n-1+k}{n-1} \end{equation} $n=2015, k=20173697$: \begin{equation} \binom{2015-1+20173697}{20173697}= \binom{20175711}{2014} \end{equation}

And that should be the answer to this part. However, there is still (2):

so that the number of bins with exactly 4 balls is 3, with exactly 7 balls is 4,

and that's where I am lost. How do I calculate this?

1

There are 1 best solutions below

0
On BEST ANSWER

You got the hard part (i.e. the Stars and Bars part) correct, but had a problem with the $~7~$ special bins.


First, I need to be sure that I have correctly interpreted the constraints:

  • There are $~20212022~$ identical balls.

  • There are $~2022~$ different bins, and the bins are distinguishable from each other.

  • There must be exactly $~4~$ bins that have exactly $~3~$ balls in them.

  • There must be exactly $~7~$ bins that have exactly $~4~$ balls in them.

  • Each of the remaining bins have at least $~19~$ balls in them.


This is a Stars and Bars problem. For Stars and Bars theory, see this article and this article.

First of all, you have to select the $~3~$ bins that will have $~4~$ balls each, and then the $~4~$ bins that will have $~7~$ balls each.

This can be done in

$$\binom{2022}{3} \times \binom{2019}{4} ~~\text{different ways}. \tag1 $$

So, the expression in (1) above is reserved as a factor to be applied, and I can now assume, without loss of generality, that the $~7~$ special bins have been determined.

Then you have $~(20212022 - 12 - 28) = 20211982 ~$ balls remaining, that must be placed in $~(2022 - 7) = 2015~$ (remaining) distinguishable bins, so that each bin has at least $~19~$ balls.

Letting $~x_k~$ denote the number of balls placed in bin-$k,~$ this implies that I need to compute the number of solutions to :

  • $x_1 + x_2 + \cdots + x_{2015} = 20211982.$

  • $x_1, ~x_2, ~\cdots, ~x_{2015} \in \Bbb{Z_{\geq 19}}.$

Basic Stars and Bars theory is based on the lower limit of the variables being $~0,~$ rather than $~19.$ The necessary adjustment is to let

$$y_i = x_i - 19 ~: ~i \in \{1,2,\cdots,2015\}.$$

Then the number of solutions to be computed is equivalent to the number of solutions to

  • $y_1 + y_2 + \cdots + y_{2015} = 20211982 - (19 \times 2015) = 20173697.$

  • $y_1, ~y_2, ~\cdots, ~y_{2015} \in \Bbb{Z_{\geq 0}}.$

Per Stars and Bars theory, the number of solutions is

$$\binom{20173697 + [2015 - 1]}{2015 - 1} = \binom{20175711}{2014}.$$

Therefore, the final enumeration is

$$\binom{2022}{3} \times \binom{2019}{4} \times \binom{20175711}{2014}.$$


Note:
The problem would have been much more difficult if any of the $~7~$ special bins had been required to have exactly $~r~$ balls, where $r \geq 20.$ Then, Inclusion-Exclusion would have been needed.

In this particular problem, there can be no intersection between the $~7~$ special bins, and the remaining bins that have at least $~19~$ balls each.

So, that complication was avoided.