The stirling number of the second kind $S(n,k)$ counts the number of partitions of the set $[n]$ into $k$ non-empty parts. I found a definition for the numbers called the $r$-associated stirling numbers of the second kind in wikipedia. These count the number of partitions of $[n]$ into $k$ non-empty parts such that all of the parts have at least $r$ elements. They seem to be "not too hard to calculate" via the recursion:


$S\_r(n+1,k)=kS\_r(n,k)+\binom{n}{r-1}S\_r(n-r+1,k-1)$.


I am interested in a very similar construction, for which I have been unable to find any references. I would like to count $F\_r(n,k)$ defined as the number of partitions of $[n]$ into $k$ non-empty parts so that each of them has size $r$ or less.


Most of all I am interested in $\sum\limits\_{k=0}^nF\_r(n,k)$, basically the number of partitions of $[n]$ into parts of size $r$ or less.


Thank you very much in advance


Regards.




---


I am aware that the problem of finding compositions of $n$ into numbers less than or equal to $k$ has been studied. But I do not think one of them can be used to compute the other.



Stirling numbers of the second kind with maximum part size
This is a routine application of the exponential formula. If $S$ is any subset of the positive integers and $f\_S(n)$ is the number of partitions of $[n]$ into parts all belonging to $S$, then
 $$ \sum\_{n\geq 0} f\_S(n) \frac{x^n}{n!}= \exp \sum\_{i\in S}\frac{x^i}{i!}. $$
Thus in your case we get $\exp \sum\_{i=1}^r \frac{x^i}{i!}$. We also have the recurrence
 $$ f\_S(n+1) =\sum\_{i\in S}{n\choose i-1}f\_S(n-i+1). $$


