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.

Improve this question
$\endgroup$
1
  • $\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
    Commented Jun 20, 2017 at 2:04

2 Answers 2

Reset to default
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). $$

Improve this answer
$\endgroup$
1
  • $\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$
    – Gorka
    Commented Feb 22, 2015 at 17:08
2
$\begingroup$

This is the so-called restricted Stirling number of the second kind.

Reference: Incomplete poly-Bernoulli numbers associated with incomplete Stirling numbers

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .