# How to compute number of ways to partition a set under certain constraints?

Let us have a set $A$ of $|A|=n$ objects. I would like to know the number of ways to partition the set into $k$ non-empty subsets. This, I believe, is given by the Stirling numbers of the second kind, $S(n,k)$. However, I have an additional constraint roughly saying that each of the subsets must have certain minimum number of elements. Formally: there are given natural numbers $l_1, ..., l_k$ and it must be possible to label the $k$ subsets of $A$ by symbols $A_i, i = 1,...,k$ such that $|A_i| \ge l_i$. Naturally, it holds that $l_i \ge 1 \forall i$ and $\sum\limits_i l_i \le n$. Any ideas how I could compute that?

• Do you count labelled (according to these constraints) partitions or those which may be labelled, regardless by how many ways? – Fedor Petrov Mar 14 '18 at 13:11
• The later. But seeing how to compute labeled would probably be also insightful. – user1747134 Mar 14 '18 at 13:40

For fixed $l_1,\dots,l_k$ and counting the labelled partitions onto $A_1,\dots,A_k$, $|A_i|\geqslant l_i$, the exponential generating function is $\prod_k \sum_{m\geqslant l_i} \frac{x^m}{m!}=\prod_k (e^x-1-x^2/2!-\dots-x^{l_i-1}/(l_i-1)!)$. Unlikely this has closed form.
• Not sure if this is counted as a closed-form but still: $$\prod_{i=1}^k \sum_{m\geq l_i}\frac{x^m}{m!}=\prod_{i=1}^k \frac{x^{l_i}}{(l_i-1)!} \int_0^1 e^{x(1-y)} y^{l_i-1} dy.$$ – Max Alekseyev Mar 15 '18 at 16:09
Stirling numbers of second kind can be expressed as the sum: $$S(n,k) = \sum_{{j_1 + j_2 + \dots + j_n = k\atop j_1 + 2 j_2 + \dots + nj_n = n}} \frac{n!}{j_1!1!^{j_1}j_2!2!^{j_2}\cdots j_n!n!^{j_n}},\qquad(\star)$$ which essentially sums over the partitions of $n$ into $k$ parts representing the subset sizes (with $j_i$ being the multiplicity of size $i$).
Let's assume that $l_1\geq l_2\geq \dots\geq l_k$. It is possible to label the subsets as required if and only if for each $i=1,2,\dots,k$, the following inequality holds: $$\sum_{t=l_i}^n j_t\geq i.$$ (Equivalently, this can be viewed as the Young diagram of the partition encoded by $j$'s containing the Young diagram of the partition $(l_1,l_2,\dots,l_k)$). Restricting the sum $(\star)$ to such partitions will yield the number of required set partitions.