2
$\begingroup$

We know that the Stirling number of the second kind is the number of ways to partition a set of $n$ objects into $k$ non-empty subsets and is denoted by $s(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}\begin{pmatrix} k\\ j \end{pmatrix}j^n$

This formula is for the case that the partitions have at least one component. I am trying to find the similar formula for the case that each partition has at least $m$ component. Does anyone have any ideas?

$\endgroup$
  • $\begingroup$ This OEIS link has data including generating functions and recurrence relations for the case $m=3$ which should help to get started and generalize to other values for $m.$ $\endgroup$ – Marko Riedel Jun 16 '17 at 0:29
  • $\begingroup$ $\{1,\cdots ,n \} = \cup_{i=1, \cdots,k}^{\bullet} P_i$ ... each of the sets $P_i$ contains at least one element & you require them to contain at least $m$ elements. Right ? ... If so it is related to the Bell Polynomials & Faa Di Bruno Formula ... see en.wikipedia.org/wiki/Fa%C3%A0_di_Bruno%27s_formula ... truncate the tuples at from $1$ to $m-1$. $\endgroup$ – Donald Splutterwit Jun 16 '17 at 0:38
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – Phicar Jun 16 '17 at 3:45
1
$\begingroup$

The first question you should be asking is where does the formula

$$ s(n,k) = \frac1{k!} \sum_{j = 0}^k \binom{k}{j} j^n (-1)^{k - j} $$

come from? Then once you understand that, perhaps you will be able to generalize.


Note that the generating function for nonempty sets is $e^x - 1 = x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$. The generating function for a set of size $k$ is $x^k/k!$. Thus the generating function for a set of size $k$ whose elements are non-empty sets is

$$ \sum_{n \ge 0} s(n,k)\frac{x^n}{n!} = \frac{(e^x - 1)^k}{k!} $$

and therefore

$$ \sum_{k \ge 0} \sum_{n \ge 0} s(n,k)\frac{x^n}{n!}y^k = \exp(y(e^x - 1)). $$

Therefore

\begin{align} s(n,k) &= \left[ \frac{x^n}{n!}y^k \right] \exp(y(e^x - 1)) \\ &= \frac{1}{k!} \left[ \frac{x^n}{n!} \right] (e^x - 1)^k \\ &= \frac{1}{k!} \left[ \frac{x^n}{n!} \right] \sum_{j = 0}^k \binom{k}{j} e^{jx}(-1)^{k - j} \\ &= \frac{1}{k!} \sum_{j = 0}^k \binom{k}{j} j^n(-1)^{k - j}. \end{align}


Let us agree to write $s_m(n,k)$ for the number of ways to partition a set of size $n$ into $k$ subsets of size at least $m$.

Then the same thing happens as before except instead of using $e^x - 1$ for non-empty sets, we use $$ e^x - 1 - x - \frac{x^2}{2!} - \dots - \frac{x^{m - 1}}{(m - 1)!} = \frac{x^m}{m!} + \frac{x^{m + 1}}{(m + 1)!} + \frac{x^{m + 2}}{(m + 2)!} + \cdots $$ for sets with at least $m$ elements. So we have

$$ \sum_{n,k} s_m(n,k)\frac{x^n}{n!}y^k = \exp \left[ y \left( e^x - 1 - x - \frac{x^2}{2!} - \dots - \frac{x^{m - 1}}{(m - 1)!} \right) \right]. $$

And like before,

\begin{align} s_m(n, k) &= \frac{1}{k!} \left[ \frac{x^n}{n!} \right] \left( e^x - 1 - x - \frac{x^2}{2!} - \dots - \frac{x^{m - 1}}{(m - 1)!} \right)^k \\ &= \frac{1}{k!} \left[ \frac{x^n}{n!} \right] \sum_{i + j_0 + \dots + j_{m - 1} = k} \binom{k}{i,j_0,\dots,j_{m-1}} e^{ix}(-1)^{j_0}\left( -x \right)^{j_1} \cdots \left( -\frac{x^{m - 1}}{(m - 1)!} \right)^{j_{m - 1}} \end{align}

Now we group together the minus signs: $(-1)^{j_0 + \dots + j_{m - 1}} = (-1)^{k - i}$ giving

\begin{align} &\frac{1}{k!}\left[ \frac{x^n}{n!} \right] \sum_{i + j_0 + \dots + j_{m - 1} = k} \binom{k}{i,j_0,\dots,j_{m-1}} e^{ix}(-1)^{k - i}\left( x \right)^{j_1} \cdots \left( \frac{x^{m - 1}}{(m - 1)!} \right)^{j_{m - 1}} \\ &= \frac{n!}{k!} \sum_{i + j_0 + \dots + j_{m - 1} = k} \binom{k}{i,j_0,\dots,j_{m-1}} \frac{1}{0!^{j_0}\cdots (m-1)!^{j_{m - 1}}} [x^n] e^{ix}(-1)^{k - i} x^{0j_0 + \dots + (m - 1)j_m} \\ &= \frac{n!}{k!} \sum_{i + j_0 + \dots + j_{m - 1} = k} \binom{k}{i,j_0,\dots,j_{m-1}} \frac{1}{1!^{j_1}\cdots (m-1)!^{j_{m - 1}}} [x^{n - 1j_1 - \dots - (m - 1)j_m}] e^{ix}(-1)^{k - i} \\ &= \frac{n!}{k!} \sum_{i + j_0 + \dots + j_{m - 1} = k} \binom{k}{i,j_0,\dots,j_{m-1}} \frac{1}{1!^{j_1}\cdots (m-1)!^{j_{m - 1}}} i^{n - j_1 - 2j_2 - \dots - (m - 1)j_{m - 1}} (-1)^{k - i}. \end{align}

$\endgroup$
  • $\begingroup$ What do you mean by $\binom{k}{i,j_0,\dots,j_{m-1}}$? And is the summation over the solutions of the equation? $\endgroup$ – Hamed Jun 16 '17 at 22:10
  • $\begingroup$ @Hamed Yes, all solutions to the equation with $i, j_0, \dots, j_{m - 1} \ge 0$ (although by definition that symbol is zero if $i, j_0,\dots,j_{m - 1}$ don't sum to $k$ or are not all non-negative. See this question. $\endgroup$ – Trevor Gunn Jun 16 '17 at 22:14

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.