1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Jun 14 at 22:27
  • $\begingroup$ By the way, if I've done the arithmetic correctly, the answer is $28125$. $\endgroup$ Jun 14 at 22:36
  • $\begingroup$ Sorry, each cell must contain 1 ball only. $\endgroup$
    – Math Horse
    Jun 14 at 22:47
  • $\begingroup$ Not all 10 balls will fit. There's an example in the thread content on how a group of 5 cells should look like. $\endgroup$
    – Math Horse
    Jun 14 at 22:48
  • $\begingroup$ 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. $\endgroup$
    – Math Horse
    Jun 14 at 22:51

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\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.