How many ways are there to distribute 12 distinguishable balls into 6 distinguishable bins?

Question

How many ways are there to distribute 12 distinguishable balls into 6 distinguishable bins so that 2 balls are placed in each bin ?

---

I solved it in the following way =>

$C(12,2) * C(10,2) * C(8,2) * C(6,2) * C(4,2) * C(2,2)$ and got the correct answer.

---

Can I apply Sterling formula of 2nd kind here ?

I want to know how Sterling formula of 2nd kind is applied here ?

Answer 1

Applying $S_2$ here will be quite convoluted.

As explained in another question of yours,
The number of ways of getting exactly k different values when you throw n fair r-sided dice is

$\binom{r}{k}\cdot S_2(n,k)\cdot k! $

so to get exactly $6$ faces in $12$ throws of a normal die, $\binom66\cdot S_2(12,6)\cdot6!$ ways,
but this would include $11$ patterns, viz.

$\boxed 7\boxed 1\boxed 1\boxed 1\boxed 1\boxed 1\;\;\boxed 6\boxed 2\boxed 1\boxed 1\boxed 1\boxed 1\;\;\boxed 5\boxed 3\boxed 1\boxed 1\boxed 1\boxed 1\;\; \boxed 5\boxed 2\boxed 2\boxed 1\boxed 1\boxed 1\;\;\boxed 4\boxed 4\boxed 1\boxed 1\boxed 1\boxed 1$

$\boxed 4\boxed 3\boxed 2\boxed 1\boxed 1\boxed 1\;\;\boxed 4\boxed 2\boxed 2\boxed 2\boxed 1\boxed 1\;\;\boxed 3\boxed 3\boxed 3\boxed 1\boxed 1\boxed 1 \;\;\boxed 3\boxed 3\boxed 2\boxed 2\boxed 1\boxed 1\;\;\boxed 3\boxed 2\boxed 2\boxed 2\boxed 2\boxed 1$

$\boxed 2\boxed 2 \boxed 2 \boxed 2 \boxed 2 \boxed 2$

and we are interested only in the last pattern.

Now the number of ways for placing $12$ distinguishable balls in $6$ bins, the bins being indistinguishable except by occupancy, the multinomial coefficient has to be divided by ${p! q!..}$ where $p$ bins each have $p_n$ balls, $q$ bins each have $q_n$ balls, etc, e.g. for $\boxed 4\boxed 2\boxed 2\boxed 2\boxed 1\boxed 1$, there are $\binom{12}{4,2,2,2,1,1}/(3!2!)$ ways.

$S_2(12,6)= 1,323,652$ From this, if we subtract number of ways for $10$ unwanted patterns, we get

$1323652 - \left[\binom{12}{7,1,1,1,1,1}/ 5!+\binom{12}{6,2,1,1,1,1,}/4! ...+\binom{12}{5,2,2,1,1,1}/(2!3!) + ... \binom{12}{3,2,2,2,2,1}/4!\right] = 10,395$

$10,395$ is the number of ways to place$2$ each of $12$ distinguishable balls in $6$ indistinguishable bins,

So $10,395\times 6! = 7,484,400$, the desired answer.

But this looks like trying to catch your nose by bringing your hand from behind your neck !

Answer 2

If you want to be 'technical', you certainly can, but they are not particularly interesting or adequate, for two reasons. The first is that Stirling numbers of the second kind count undistinguishable bins. The second is that they do not take into account bin size (apart from a bin being nonempty), only number of bins.

It would be much better if you used Multinomial coefficients for this kind of problem (which is exactly what you did, if we carefully inspect your solution).

Answer 3

The number I think of immediately is the multinomial coefficient $$ \begin{align} \binom{12}{2,2,2,2,2,2} &=\frac{12!}{2!\,2!\,2!\,2!\,2!\,2!}\\[6pt] &=7484400 \end{align} $$ which can be computed from binomial coefficients as you have done.

---

However, if you want to use Stirling Numbers of the Second Kind and avoid multinomial coefficients, we can compute the number of partitions of $12$ items with no singleton using Inclusion-Exclusion: The number of ways to partition a set of $12$ items into $6$ subsets with $k$ specific singletons is $$\newcommand{\stirtwo}[2]{\left\{#1\atop#2\right\}} \overbrace{\ \ \ \ \binom{12}{k}\ \ \ \ }^{\substack{\text{number of ways to}\\\text{choose the singletons}}}\overbrace{\ \ \stirtwo{12-k}{6-k}\ \ }^{\substack{\text{number of ways to}\\\text{partition the rest}}} $$ By Inclusion-Exclusion, there are then $$ \sum_{k=1}^6(-1)^{k-1}\binom{12}{k}\stirtwo{12-k}{6-k} $$ ways to partition $12$ items into 6 subsets with at least one singleton. Since there are $\stirtwo{12}{6}$ ways to partition $12$ items into 6 subsets, we have $$ \begin{align} &\stirtwo{12}{6}-\sum_{k=1}^6(-1)^{k-1}\binom{12}{k}\stirtwo{12-k}{6-k}\\ &=\sum_{k=0}^6(-1)^k\binom{12}{k}\stirtwo{12-k}{6-k} \end{align} $$ ways to partition $12$ items into 6 subsets with no singletons; that is, into $6$ pairs. However, this does not count the orderings of these $6$ pairs, so we need to multiply this number by $6!$. That is, $$ \begin{align} &6!\sum_{k=0}^6(-1)^k\binom{12}{k}\stirtwo{12-k}{6-k}\\[3pt] &=6!\left[{\textstyle\binom{12}{0}\stirtwo{12}{6}-\binom{12}{1}\stirtwo{11}{5}+\binom{12}{2}\stirtwo{10}{4}-\binom{12}{3}\stirtwo{9}{3}+\binom{12}{4}\stirtwo{8}{2}-\binom{12}{5}\stirtwo{7}{1}+\binom{12}{6}\stirtwo{6}{0}}\right]\\[9pt] &=720\,[{\small1\cdot1323652-12\cdot246730+66\cdot34105-220\cdot3025+495\cdot127-792\cdot1+924\cdot0}]\\[9pt] &=720\cdot10395\\[10pt] &=7484400 \end{align} $$