2
$\begingroup$

I just discovered associated Stirling numbers of the second kind, and I was curious if there has been any formula or asymptotic analysis done on the following variation:

"The number of ways to partition a set of $n$ objects into $k$ subsets, with each subset containing at least $1$, and at most $r$, elements."

In particular, I'm curious if any sort of formula (recurrence relation, summation, or anything really), or an asymptotic upper bound exist for this concept.

$\endgroup$
  • $\begingroup$ @bof Yes, that is exactly what I meant. I have amended the question appropriately. Would you be able to link me to (or give) an explanation of how you arrived at that equation as well? $\endgroup$ – Koz Ross Dec 30 '17 at 6:05
  • 2
    $\begingroup$ It's an instance of a general formula for this sort of problem. If $A$ is a set of nonnegative integers and $B$ a set of positive integers, and $c_n$ is the number of ways a set of $n$ objects can be partitioned so that the number of parts is in $A$ ane the size of each part is in $B,$ then $$\sum_{n=0}^\infty\frac{c_nx^n}{n!}=A(B(x))$$ where $$A(x)=\sum_{n\in A}\frac{x^n}{n!}\text{ and }B(x)=\sum_{n\in B}\frac{x^n}{n!}.$$ For example, if $A$ is the set of all nonnegative integers and $B$ the set of all positive integers, we get $e^{e^x-1}$ as the e.g.f. of the Bell numbers. $\endgroup$ – bof Dec 30 '17 at 6:24
  • $\begingroup$ @bof Does this general formula have a name of some kind? $\endgroup$ – Koz Ross Dec 30 '17 at 6:28
  • $\begingroup$ I also don't know if this has a name. This is part of the "yoga" of exponential generating functions, and any book treating exponential generating functions will hopefully explain something like it. $\endgroup$ – Qiaochu Yuan Dec 30 '17 at 8:10
  • $\begingroup$ I still don't know if that formula has a name, but I found a reference. See equation (2.5) in Lars Holst, On numbers related to partitions of unlike objects and occupancy problems, Europ. J. Combinatorics 2 (1981), 231–237. @QiaochuYuan $\endgroup$ – bof Jan 1 '18 at 2:46

Your Answer

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

Browse other questions tagged or ask your own question.