4
$\begingroup$

A different summation formula represents each Bell number as a sum of Stirling numbers of the second kind

$ B_n=\sum_{k=0}^n \left\{{n\atop k}\right\} $

The Stirling number $\left\{{n\atop k}\right\} $ is the number of ways to partition a set of cardinality n into exactly k nonempty subsets. Thus, in the equation relating the Bell numbers to the Stirling numbers, each partition counted on the left hand side of the equation is counted in exactly one of the terms of the sum on the right hand side, the one for which k is the number of sets in the partition.

I was reading wiki and found the summation starts from $0$ instead of $1$. Is not that logically incorrect? Set partition never allowed to be empty. Can anybody clarify?

Thanks :)

$\endgroup$
4
$\begingroup$

The Stirling number $n\brace k$ is actually defined for all pairs of non-negative integers. Of course ${n\brace k}=0$ when $k>n$. Since a non-empty set cannot have a partition into $0$ parts, it’s also clear that we want ${n\brace 0}=0$ for $n>0$. It turns out, however, to be convenient to set ${0\brace 0}=1$, as it makes recurrence

$${{n+1}\brace k}=k{n\brace k}+{n\brace{k-1}}$$

behave nicely.

$\endgroup$
  • $\begingroup$ @ViX28: You’re welcome. $\endgroup$ – Brian M. Scott Apr 4 '16 at 19:03

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.