5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$$ $\endgroup$ – videlity Jun 20 '17 at 2:04
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jorge Fernández Feb 22 '15 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.