Dobiإ„ski’s formula

A derivation of Dobiإ„ski’s formula is reproduced below. Why does the upper limit on the first sum change from nn to ∞\infty ? (See the red-boxed portion.)




have you seen the change of integration for a double integral? I assume he permuted the order to take advantage of the close form of the inner summation.
– Chinny84
Oct 20 at 19:50



Exactly, +∞∑k=1k∑j=0\sum_{k=1}^{+\infty}\sum_{j=0}^{k} is turned into +∞∑j=0∑k≥j\sum_{j=0}^{+\infty}\sum_{k\geq j}
– Jack D’Aurizio
Oct 20 at 20:32



In such a question, you should recall that B(n)B(n) is the nnth Bell number with a reference to a definition/explanation such as can be found in (إ„ski’s_formula). It is important that a text is self-contained.
– JeanMarie
Oct 20 at 21:24


1 Answer


The point is that the inner sum is 00 when k>nk>n.

In fact, the inner sum ∑kj=0(−1)k−j(kj)jn\sum_{j=0}^k (-1)^{k-j} {k\choose j} j^n is just k!S(n,k)k!S(n,k), where S(n,k)S(n,k) is the Stirling number of the second kind, which counts the number of ways of partitioning a set of nn elements into kk nonempty subsets. Clearly, S(n,k)=0S(n,k)=0 when k>nk>n.

Also important for the reindexing is that S(n,0)=0S(n,0)=0 when n>0n>0, otherwise there would be a problem in the second step.

It would probably be simpler if we just wrote, from the start, B(n) = \sum_{k=0}^\infty S(n,k)B(n) = \sum_{k=0}^\infty S(n,k), which is valid for n\geq 0n\geq 0.