1
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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.$$ $\endgroup$ – Max Alekseyev Mar 15 '18 at 16:09
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.