1

There is a basket with the following amount of balls and it's types: $2\times A$, $2 \times B$, $3 \times C$, $3 \times D$ . In total, there are $10$ balls.

I am looking for a way to calculate how many possible distributions of these $10$ balls to $5$ cells are possible. Order does not matter.

To make myself clearer: $\{A, A, B, B, C\} = \{A, B, A, C, B\}$. So similar combinations but in a different order, should be counted one time only. Each cell must contain $1$ ball only.

I have tried solving with $D(n,k)$ and $\frac{10!}{ 2!2!3!3!}$, but after a manual check I have performed on a mini-problem similar to this one, I've came to a conclusion that these methods are wrong to use for this problem.

Thanks in advance.

N. F. Taussig
  • 76,571
Math Horse
  • 23
  • Are you saying that the cells are distinguishable but that balls of the same type are not distinguishable from one another? So, for example, all $10$ balls in the first cell is a different arrangement than all $10$ balls in the second cell? In any event, please show us what you've tried and what techniques are available to you. Questions that don't show some independent effort to reach a solution usually aren't well received here. – Robert Shore Jun 14 '22 at 22:27
  • By the way, if I've done the arithmetic correctly, the answer is $28125$. – Robert Shore Jun 14 '22 at 22:36
  • Sorry, each cell must contain 1 ball only. – Math Horse Jun 14 '22 at 22:47
  • Not all 10 balls will fit. There's an example in the thread content on how a group of 5 cells should look like. – Math Horse Jun 14 '22 at 22:48
  • Okay, so I have tried d(n,k) and received 1001 if I'm not mistaken. Also tried 10! Devided by 2!2!3!3! And received 25200. Feels like those are wrong approaches. I checked myself by lowering the cell and ball type count and manually counting a smaller problem. – Math Horse Jun 14 '22 at 22:51

2 Answers2

1

As noted, you want to know the number of solutions of $x_A+x_B+x_C+x_D=5$ in non-negative integers with constraints. Stars and bars tells you that there are $\binom 85=56$ unconstrained solutions to this equation. But we have to subtract off the solutions that violate one or more of the constraints.

How many solutions to the unconstrained equation have $x_A \geq 3$? That is equivalent to the number of solutions of $y_A+x_B+x_C+x_D=2$ in non-negative integers (where $y_A=x_A-3$). Stars and bars tells us there are $\binom 52=10$ "forbidden" solutions of that type. Similarly there are another $10$ forbidden solutions with $x_B \geq 3$.

A similar analysis tells us that there are $4$ forbidden solutions with $x_C \geq 4$ and $4$ more forbidden solutions with $x_D \geq 4$. No solution to the original equation can violate two or more constraints, so there is no overlap between the forbidden solutions.

Thus, there are $56-(10+10+4+4)=28$ acceptable solutions.

Robert Shore
  • 23,332
1

The number of ways we can pick an 'A' ball is either $0, 1$ or $2$. Using generating functions , this is written as

$$1+x+x^2$$

In order to create the generating function for the whole scene, we multiply each GF per ball type together:

$$(1+x+x^2)(1+x+x^2)(1+x+x^2+x^3)(1+x+x^2+x^3)$$

This equates to

$$x^{10} + 4 x^9 + 10 x^8 + 18 x^7 + 25 x^6 + 28 x^5 + 25 x^4 + 18 x^3 + 10 x^2 + 4 x + 1$$

The coefficient of $x$ tells us the number of balls required, in this case $n=5$, and the answer is $28$.

JMP
  • 21,771