# Generalised Stirling number that each partition has more than one component

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?

• 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.$ – Marko Riedel Jun 16 '17 at 0:29
• $\{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$. – Donald Splutterwit Jun 16 '17 at 0:38
• en.wikipedia.org/wiki/… – Phicar Jun 16 '17 at 3:45

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}

• What do you mean by $\binom{k}{i,j_0,\dots,j_{m-1}}$? And is the summation over the solutions of the equation? – Hamed Jun 16 '17 at 22:10
• @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. – Trevor Gunn Jun 16 '17 at 22:14