Ways of carrying balls

141 Views Asked by At

There are $10$ balls numbered $1,2,\ldots,10$. There are two students with two identical bags each. In how many ways can they carry the balls in their bags so that no bag is empty?

So, there are two sets of two identical bags, say A,A and B,B I am arranging numbers from 1 to 10 in $10!$, then putting 3 bars in $C(10,3)$ ways in the arrangement of numbers such that balls placed with and on the left of first bar goes to bag A, balls placed with and between the first bar goes to second bag B, and so on. Now, dividing by $2!×2!$ because we have two sets of two identical bags. So, we get $10!\times C(10,3)/(2!)^{2}$

Please check if it is correct. Thanks!

Edit:

I am overcounting in the method I have used above, as there arrangement of balls inside the bags will also matter. Now, I think the correct solution would be $4!\times S(10,4)/(2!)^{2}$. The idea is to count onto functions from $10-set$ to $4-set$, then set of preimages of $1$ and $2$, and $3$ and $4$ can be arranged in $2!$ ways each, so dividing by $2!\times 2!$.

1

There are 1 best solutions below

1
On BEST ANSWER

Your second answer is correct (assuming $S(10,4)$ means Stirling numbers of the second kind).

$${4! \over 2! 2!} \times S(10,4) = 6 \times 34105 = 204630$$

An alternative is to count using inclusion-exclusion. The number of ways to place the balls, into $4$ distinguishable bags, without any bag being empty is:

$$4^{10} - {4 \choose 1} \times 3^{10} + {4 \choose 2} \times 2^{10} - {4 \choose 3} \times 1^{10} = 818520$$

Divide $818520$ by $2! \times 2!$ for the bag-swaps and you get the same $204630$.