# Question in Combinatorics, Arrange 10 balls (4 different types) between 5 cells. Order doesn't matter.

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.

• 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. Jun 14 at 22:27
• By the way, if I've done the arithmetic correctly, the answer is $28125$. Jun 14 at 22:36
• Sorry, each cell must contain 1 ball only. Jun 14 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. Jun 14 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. Jun 14 at 22:51

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

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.