number of partitioning an $n$-set into subsets of a particular size

83 Views Asked by At

We know that the number of ways that an $n$-set can be partitioned into $k$ non-empty subsets is given by the Stirling number of the second kind, i.e., $\left\{\begin{array}{c}n\\k\end{array}\right\}$. Now, what's the number of ways that one may partition an $n$-set into $k$ subsets of sizes $n_1,n_2,\ldots,n_k$ when the order of the subsets does not matter?

Let's denote that number by $B_n(n_1,n_2,\ldots,n_k)$. Obviously, $B_n(n_1,n_2,\ldots,n_k)$ is nonzero only when $n_1+n_2+\ldots+n_k=n$. Therefore, one may drop the subscript $n$ and show the described number by $B(n_1,n_2,\ldots,n_k)$. Does this number have a particular name in combinatorics?

The same question has been asked here, but the answer given to that question is for the case that the order of subsets is important. Indeed, if the order of subsets is important then the number of ways that one may partition an $n$-set into subsets of size $n_1,n_2,\ldots,n_k$ is given by $$\left(\begin{array}{c}n\\n_1,n_2,\ldots,n_k\end{array}\right).$$

Example 1: $B(2,2)=3$ since the only partitions of the set $\{a,b,c,d\}$ into subsets of size $2$ are $$\big\{\{a,b\},\{c,d\}\big\},\quad\big\{\{a,c\},\{b,d\}\big\},\quad\text{and}\quad\big\{\{a,d\},\{b,c\}\big\}.$$ Note that $\left(\begin{array}{c}4\\2,2\end{array}\right)=6$.

Example 2: $B(2,3)=10$. Note that in this case, $B(2,3)=\left(\begin{array}{c}5\\2,3\end{array}\right)$.

1

There are 1 best solutions below

2
On BEST ANSWER

Talking about partitioning into sets of size $n_1,n_2,\dots,n_k$, let us organize these in terms of their size and group same-sized numbers together. Notation can get messy if I try to be particularly careful so I'll be handwavy and relabel this list $n_{a_1},n_{a_2},\dots,n_{a_\alpha},n_{b_1},n_{b_2},\dots,n_{b_\beta},\dots$ where each of the $n_{a_i}=n_{a_j}$ are all equal but $n_{a_i}\neq n_{b_j}$ and so on... Recognize that each outcome you hope to count was counted $\alpha!\beta!\cdots$ times if we used multinomial coefficients, once for each different relabelings of the parts in the partition within each size-category.

So, the modified count is $$\binom{n}{n_{a_1},n_{a_2},\dots,n_{a_\alpha},n_{b_1},\dots,n_{b_\beta},\dots}\cdot\frac{1}{\alpha!\beta!\cdots}$$

Note, $\binom{4}{2,2}\cdot\frac{1}{2!}=3$ and $\binom{5}{2,3}\cdot\frac{1}{1!1!}=10$ etc...