Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Qiaochu Yuan Jun 30 at 6:35
1  
Btw, the Lang reference in my answer with proofs of Qiaochu's and Zurab's assertions came from the OEIS entry. –  Tom Copeland Jul 1 at 10:43
    
@TomCopeland True; I had not noticed it before. –  Amritanshu Prasad Jul 2 at 3:48

4 Answers 4

up vote 14 down vote accepted

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)}.$$

share|improve this answer

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.

share|improve this answer
2  
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. –  Qiaochu Yuan Jun 30 at 6:55
    
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. –  Pietro Majer Jul 1 at 10:48
1  
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$). –  Richard Stanley Jul 6 at 13:54

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}.$$

share|improve this answer
    
The restrictions on s and t are more stringent for some sums, of course. –  Tom Copeland Jul 8 at 10:12

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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