Counting partitions of a finite set in $\lambda_j$ $j$-element sets

161 Views Asked by At

Suppose we have an $n$-element set $A$ and $\lambda_1,\dots,\lambda_n \in \mathbb{N}_0$ with $\sum_{i=1}^n \lambda_i\cdot i = n$.

How many partitions $P$ of $A$ are there, s.t. $\# \binom{A}{j} = \lambda_j$ for all $j\in \{1,\dots,n\}$, i.e. s.t. there are $\lambda_j$ $j$-element sets in $P$ for $j = 1,\dots, n$?

My idea was roughly like this:

First you choose one-element subsets of $A$, that is: you choose $1$ from $n$ elements, then $1$ from $n-1$, ..., then $1$ from $n-\lambda_1+1$. Then you continue with two-element subsets: you choose $2$ from the remaining $n-\lambda_1$ elements, then $2$ from $n-\lambda_2-2$, ... then $2$ from $n-\lambda_1-\lambda_2+2$. This continues until you (possibly) choose an $n$-element set. This leaves me with: $\binom{n}{1} \cdot \binom{n-1}{1} \dots \binom{n-\lambda_1+1}{1}\cdot \binom{n-\lambda_1}{2} \dots \binom{n - \sum_{i=1}^{n-1} \lambda_i\cdot i}{n}$ partitions.

But I think my argument is wrong somehow. If possible, I'd like to see a proof or at least convincing handwaving for any claim made.

1

There are 1 best solutions below

0
On BEST ANSWER

The first task is to count the ways to partition $[n]$ into sets $A_k$ for $k=1,\ldots,n$ such that $|A_k|=k\lambda_k$. Let $m_k=k\lambda_k$ for $k=1,\ldots,n$; there are

$$\binom{n}{m_1,m_2,\ldots,m_n}=\frac{n!}{m_1!m_2!\ldots m_n!}$$

ways to choose the sets $A_k$.

Now we have to count the ways to partition each $A_k$ into $\lambda_k$ subsets, each of size $k$. $A_k$ is a subset of $[n]$, it has a natural order. We first pick the smallest element of $A_k$ and choose $k-1$ of the remaining $m_k-1$ elements to be combined with it into a set of cardinality $k$; this can be done in $\binom{m_k-1}{k-1}$ ways. We then pick the smallest of the remaining $m_k-k$ elements and choose $k-1$ of the other $m_k-k-1$ remaining elements to be combined with it; this can be done in $\binom{m_k-k-1}{k-1}$ ways. We repeat the procedure until we’ve formed all $\lambda_k$ $k$-subsets of $A_k$. The whole task can be carried out in

$$\prod_{i=0}^{\lambda_k-1}\binom{m_k-ik-1}{k-1}$$

ways. This looks a bit messy, but it can be simplified:

$$\prod_{i=0}^{\lambda_k-1}\binom{m_k-ik-1}{k-1}=\prod_{i=0}^{\lambda_k-1}\frac{(m_k-ik-1)^{\underline{k-1}}}{(k-1)!}\;,$$

where $x^{\underline\ell}$ is a falling factorial. When this is multiplied out, the numerator is $m_k!$ without the factors that are multiples of $k$, which is

$$\frac{m!}{k^{\lambda_k}\lambda_k!}\;.$$

The whole thing is therefore

$$\frac{m_k!}{k^{\lambda_k}\lambda_k!(k-1)!^{\lambda_k}}=\frac{m_k!}{\lambda_k!k!^{\lambda_k}}\;.$$

Putting all the pieces together, we find the total number of partitions of the desired shape is

$$\binom{n!}{m_1!m_2!\ldots m_n!}\prod_{k=1}^n\frac{m_k!}{\lambda_k!k!^{\lambda_k}}=\frac{n!}{\prod_{k=1}^n\lambda_k!k!^{\lambda_k}}=\prod_{k=1}^n\frac{k}{\lambda_k!k!^{\lambda_k}}\;.$$