15
$\begingroup$

In the OEIS entry for Bell numbers, there appears a generating function

$$\sum_{k=0}^\infty B_k t^k = \sum_{r=0}^\infty \prod_{i=1}^r \frac{t}{1-it}$$

However, I could not locate any proof of reference for this formula. The contributor informs me that he discovered it by experimentation.

I would appreciate any further information on this generating function.

$\endgroup$
3
  • $\begingroup$ An experimental approach here is to truncate the sum and see what numbers you get, then pop those numbers back in the OEIS to see if they count anything recognizable. Also, the RHS looks like it's Stirling numbers of the second kind. $\endgroup$ Jun 30, 2014 at 6:35
  • 1
    $\begingroup$ Btw, the Lang reference in my answer with proofs of Qiaochu's and Zurab's assertions came from the OEIS entry. $\endgroup$ Jul 1, 2014 at 10:43
  • $\begingroup$ @TomCopeland True; I had not noticed it before. $\endgroup$ Jul 2, 2014 at 3:48

4 Answers 4

19
$\begingroup$

The proof is given, for example, in http://www.sciencedirect.com/science/article/pii/S0097316503000141 (Bell numbers, their relatives, and algebraic differential equations, by Martin Klazar). Namely it is proved that the generating function $B(t)=\sum\limits_{n=0}^\infty B_nt^n$ satisfies the functional equation $$B(t)=1+\frac{t}{1-t}B\left(\frac{t}{1-t}\right).$$ Iterating this equation, we get (Klazar calls it the classical expansion of B(t)) $$B(t)=\sum\limits_{n=0}^\infty \frac{t^n}{(1-t)(1-2t)\cdots(1-nt)}.$$

$\endgroup$
15
$\begingroup$

Let $S_{n, k}$ denote the number of partitions of a set of size $n$ into $k$ partitions (the Stirling numbers of the second kind), so that $B_n = \displaystyle \sum_{k=0}^n S_{n, k}$ and hence, exchanging the order of summation, we have

$$\sum_{n=0}^{\infty} B_n t^n = \sum_{n=0}^{\infty} \sum_{k=0}^n S_{n, k} t^n = \sum_{k=0}^{\infty} t^k \sum_{n=k}^{\infty} S_{n, k} t^{n-k}.$$

A standard identity whose proof I used to know but have now forgotten asserts that

$$\sum_{n=k}^{\infty} S_{n, k} t^{n-k} = \frac{1}{(1 - t)(1 - 2t)\cdots(1 - kt)}$$

and this gives your formula. This is identity 1.94c in the second edition of Stanley's Enumerative Combinatorics, Volume I.

$\endgroup$
3
  • 3
    $\begingroup$ Here's a sketch of a combinatorial proof. For fixed $k$ we want to count how to partition a set of some size into $k$ nonempty partitions. Order the set and mark each point in the order at which a new partition occurs; this is the factor $t^k$ in the generating function. Between the appearance of partition $i$ and partition $i+1$ the points in the set can be in any of the first $i$ partitions; this is the factor $\frac{1}{1 - it}$ in the generating function. $\endgroup$ Jun 30, 2014 at 6:55
  • 2
    $\begingroup$ It should also follow plainly from the recurrence relation $S(n+1,k)=kS(n,k)+S(n,k-1)$ --which is of course of the same combinatorial nature. $\endgroup$ Jul 1, 2014 at 10:48
  • 2
    $\begingroup$ As an aside, let $G(t)=\sum_{n\geq 0}B_nt^n$. Then the solution to Exercise 1.111 of Enumerative Combinatorics, vol. 1, shows that $(1-t)G(t(1-t))$ is the ordinary generating function for the number of partitions of $1,2,\dots,n$ such that no block is an interval $a,a+1,\dots,b$ (including the case $a=b$). $\endgroup$ Jul 6, 2014 at 13:54
10
$\begingroup$

As a general remark, we may see the "Exponential to Ordinary" transformation of generating functions, $$ f(x):=\sum_{r=0}^\infty a_rx^r/r!\mapsto \tilde f(t):=\sum_{r=0}^\infty a_rt^r, $$ as an operator $\mathbb{C}[[x]]\to \mathbb{C}[[t]]$ . Since $r!t^r=\int_0^\infty (tx)^r e^{-x}dx$, the transformation can be computed analytically as $$\tilde f(t)=\int_0^\infty f(tx)e^{-x}dx,$$ at least for suitably convergent $f(x)$, and for special values of $t$. If the RHS is a convergent series $\sum_{r=0}^\infty b_rt^r$, and the equality holds, for a set of values $t$ which accumulates within the disk of convergence, the identity of series $ \sum_{r=0}^\infty a_rt^r=\sum_{r=0}^\infty b_rt^r$ is then established by the principle of isolated zeros.

For instance, we may compute the transform of $f_r(x):=(e^x-1)^r$ for real negative values of $t$ in terms of the Euler's Beta function by a change of variable in the integral:
$$\tilde f_r(t)=\int_0^\infty (e^{tx}-1)^re^{-x}dx=(-1)^{r+1}t^{-1}\int_0^1(1-u)^r u^{-1/t-1}du=$$ $$=(-1)^{r+1}t^{-1}\frac{\Gamma(r+1)\Gamma(-1/t)}{\Gamma(r+1-1/t)}=\frac{r!t^r}{(1-t)\dots(1-rt)}\ .$$ This computation gives your identity, since for the egf $f(x)$ of the $B_r$'s we have $f(x)=e^{e^x-1}=\sum_{r=0}^\infty\frac{1}{r!}f_r(x)$ (in the sense of formal power series) so that $\tilde f(t)=\sum_{r=0}^\infty \frac{t^r}{(1-t)\dots(1-rt)}\ .$

Incidentally, note that by an analogous computation you may, more generally, compute the ordinary gf of the Stirling polynomials of the second kind, $B_r(z) :=\sum_{r=0}^nS(n,r)z^r$, starting by their egf $e^{z(e^x-1)}$.

rmk. I think a more natural proof is, computing directly the ogf of the Stirling polynomials $B_r(z):=\sum_{r=0}^nS(n,r)z^r$, which consists just in translating the inductive relation $S(n+1,k)=kS(n,k)+S(n,k−1)$ in the language of formal power series, and then putting $z=1$, as done in other answers. The present answer is meant as an example of a general alternative approach.

$\endgroup$
8
$\begingroup$

You can also approach a proof of a more general relation using the generalized Dobinski formula:

$$f(\phi.(x))= e^{-x}exp(a.x)=exp(-(1-a.)x),$$

where $(\phi.(x))^n=\phi_n(x)$ is the $n$th Bell polynomial with $B_n=\phi_n(1)$ and $(a.)^n=a_n=f(n)=f(x)|_{x=n}.$

Then $$\sum_{k=0}^\infty\phi_k(x) t^k=\frac{1}{1-\phi.(x)t}=e^{-x}\sum_{n=0}^\infty\frac{1}{1-nt}\frac{x^n}{n!}$$ $$=\sum_{n=0}^\infty \frac{x^n}{n!}\sum_{j=0}^n(-1)^{n-j}\binom{n}{j}\frac{1}{1-jt}.$$

And, the last finite difference expression is the partial fraction expansion of $n!\prod_{j=1}^n \frac{t}{1-jt}$, so

$$\sum_{k=0}^\infty\phi_k(x) t^k=1+\sum_{n=1}^\infty x^n \prod_{j=1}^n \frac{t}{1-jt},$$

which reduces to the illustrated formula when $x=1$.

Other proofs, including those alluded to in other answers, can be found in W. Lang's notes.

The generalized Dobinski relation is a consequence of $$f(\phi.(:xD:))x^n=f(xD)x^n=f(n)x^n=a_n x^n=(a.x)^n,$$ where $D=d/dx$ and $(:xD:)^k=x^kD^k$ by definition, so

$$f(\phi.(:xD:))e^x=e^xf(\phi.(x))=f(xD)e^x=e^{a.x}.$$

The umbral compositional inverse of the Bell / Touchard polynomial $\phi_n(x)$ is the falling factorial / Pochhammer symbol $(s)_n=s!/(s-n)!$, i.e., $\phi_n((s).)=s^n$ and $(\phi(x).)_n=x^n$, so a dual equation shadows that of the ordinary generating function above (for $t \leq0$ and $s\geq 0$):

$$\sum_{k=0}^\infty\phi_k((s)_.) t^k=\sum_{k=0}^\infty s^k t^k=\frac{1}{1-st}$$ $$=\sum_{n=0}^\infty(-1)^n \binom{s}{n}\sum_{j=0}^n(-1)^j\binom{n}{j}\frac{1}{1-jt}$$ $$=1+\sum_{n=1}^\infty (s)_n \prod_{j=1}^n \frac{t}{1-jt}.$$

$\endgroup$
1
  • $\begingroup$ The restrictions on s and t are more stringent for some sums, of course. $\endgroup$ Jul 8, 2014 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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