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.
 A: 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.
