# Stirling numbers of the second kind with maximum part size

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.

• Did you manage to find an answer? I asked a similar question on maths stack exchange here. math.stackexchange.com/questions/2302204/… There is a recurrence there but I haven't found a way to solve it. $$F_r(n+1,k)=kF_r(n,k)+F_r(n,k−1)−{n\choose r}F_r(n−m,k−1) \qquad n,k≥1$$ – videlity Jun 20 '17 at 2:04

## 1 Answer

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).$$

• Thank you very much. Do you know if there is a simpler way to calculate $\sum\limits_{k=0}^nF_r(n,k)$? Other than writing up the recurrence for the individual $F_r(n,k)$ and adding? – Onir Feb 22 '15 at 17:08