# Number of ways to partition a set with $n$ elements to $k$ subsets where at least one subset has $r$ elements

I'm familiar with Stirling numbers of the second kind to compute the number of ways to partition a set with $n$ elements into $k$ non-empty, disjoint subsets.

However, there are combinations which I would like to forbid, e.g. any partitions where a subset with 2 elements occur. I thought about using $r$-associated Stirling numbers of the second kind $S_r(n,k)$, i.e. where all subsets have at least $r$ elements, but I cannot catch all cases with this.

So how can one write down a recurrence relation for the number of ways to partition a set with $n$ elements into $k$ subsets, where a subset exists which has $r$ elements? If this result is known, I would be grateful for a link to OESIS or something similar. I feel like it shouldn't be too hard, but I'm really bad with combinatorics.

-

The bivariate generating function of the Stirling numbers of the second kind is given by $$G(z,u) = \exp(u(\exp(z)-1))$$ so that $$n! [z^n][u^k] G(z, u) = {n \brace k}.$$ If you want to forbid subsets of $r$ elements, mark them and the generating function becomes $$H(z,u) = \exp\left(uv\frac{z^r}{r!} - u \frac{z^r}{r!} + u(\exp(z)-1)\right) = \exp\left(uv\frac{z^r}{r!} - u \frac{z^r}{r!}\right)G(z,u).$$ This has the property that the coefficient of $[v^0]$ is the generating function of the partitions with sets of size $r$ not allowed, which is $$[v^0] H(z, u) = [v^0] \exp\left(uv\frac{z^r}{r!} \right) \exp\left(-u\frac{z^r}{r!} \right) G(z,u) \\= \exp\left(-u\frac{z^r}{r!} \right) G(z,u) .$$ Now extracting the coefficient of $[z^n]$ from this we find $$n! \sum_{q=0}^{\lfloor n/r\rfloor} \frac{1}{q!} \left(-\frac{u}{r!}\right)^q [z^{n-qr}] G(z, u) .$$ We then obtain for the coefficient of $[u^k]$ the formula $$n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{(-1)^q}{q!\times (r!)^q} [u^{k-q}] [z^{n-qr}] G(z, u) \\= n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{1}{(n-qr)!} \frac{(-1)^q}{q!\times (r!)^q} [u^{k-q}] (n-qr)! [z^{n-qr}] G(z, u) \\ = n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{1}{(n-qr)!} \frac{(-1)^q}{q!\times(r!)^q} {n-qr \brace k-q}.$$ This formula gives the number of set partitions of $n$ elements into $k$ sets with subsets of size $r$ not allowed. Subtract this from ${n\brace k}$ to get the number of partitions where there is at least one subset of $r$ elements.
The OEIS has the case of $k=2$ and $r=1$, the case of $k=3$ and $r=1$ and the case of $k=4$ and $r=1$.
Observation. There is an interesting sanity check here, namely what happens when $r>n$. In this case the formula should produce ordinary Stirling numbers because forbidding subsets of a size larger than the total count of available elements does not affect the statistic. And indeed we have $\lfloor n/r \rfloor = 0$ so that only $q=0$ contributes, giving $$n! \frac{1}{n!} \frac{1}{1\times(r!)^0} {n\brace k} = {n\brace k},$$ so the check goes through and we get the correct value.