15

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

k=0Bktk=r=0ri=1t1it

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.

Tom Copeland
  • 9,937
  • 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 '14 at 06: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 01 '14 at 10:43
  • @TomCopeland True; I had not noticed it before. – Amritanshu Prasad Jul 02 '14 at 03:48

4 Answers4

19

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)=n=0Bntn satisfies the functional equation B(t)=1+t1tB(t1t). Iterating this equation, we get (Klazar calls it the classical expansion of B(t)) B(t)=n=0tn(1t)(12t)(1nt).

Zurab Silagadze
  • 16,340
  • 1
  • 47
  • 92
15

Let Sn,k denote the number of partitions of a set of size n into k partitions (the Stirling numbers of the second kind), so that Bn=nk=0Sn,k and hence, exchanging the order of summation, we have

n=0Bntn=n=0nk=0Sn,ktn=k=0tkn=kSn,ktnk.

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

n=kSn,ktnk=1(1t)(12t)(1kt)

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

Qiaochu Yuan
  • 114,941
  • 3
    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 tk 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 11it in the generating function. – Qiaochu Yuan Jun 30 '14 at 06:55
  • 2
    It should also follow plainly from the recurrence relation S(n+1,k)=kS(n,k)+S(n,k1) --which is of course of the same combinatorial nature. – Pietro Majer Jul 01 '14 at 10:48
  • 2
    As an aside, let G(t)=n0Bntn. Then the solution to Exercise 1.111 of Enumerative Combinatorics, vol. 1, shows that (1t)G(t(1t)) is the ordinary generating function for the number of partitions of 1,2,,n such that no block is an interval a,a+1,,b (including the case a=b). – Richard Stanley Jul 06 '14 at 13:54
10

As a general remark, we may see the "Exponential to Ordinary" transformation of generating functions, f(x):=r=0arxr/r!˜f(t):=r=0artr, as an operator C[[x]]C[[t]] . Since r!tr=0(tx)rexdx, the transformation can be computed analytically as ˜f(t)=0f(tx)exdx, at least for suitably convergent f(x), and for special values of t. If the RHS is a convergent series r=0brtr, and the equality holds, for a set of values t which accumulates within the disk of convergence, the identity of series r=0artr=r=0brtr is then established by the principle of isolated zeros.

For instance, we may compute the transform of fr(x):=(ex1)r for real negative values of t in terms of the Euler's Beta function by a change of variable in the integral:
˜fr(t)=0(etx1)rexdx=(1)r+1t110(1u)ru1/t1du= =(1)r+1t1Γ(r+1)Γ(1/t)Γ(r+11/t)=r!tr(1t)(1rt) . This computation gives your identity, since for the egf f(x) of the Br's we have f(x)=eex1=r=01r!fr(x) (in the sense of formal power series) so that ˜f(t)=r=0tr(1t)(1rt) .

Incidentally, note that by an analogous computation you may, more generally, compute the ordinary gf of the Stirling polynomials of the second kind, Br(z):=nr=0S(n,r)zr, starting by their egf ez(ex1).

rmk. I think a more natural proof is, computing directly the ogf of the Stirling polynomials Br(z):=nr=0S(n,r)zr, which consists just in translating the inductive relation S(n+1,k)=kS(n,k)+S(n,k1) 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.

Pietro Majer
  • 56,550
  • 4
  • 116
  • 260
8

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

f(ϕ.(x))=exexp(a.x)=exp((1a.)x),

where (ϕ.(x))n=ϕn(x) is the nth Bell polynomial with Bn=ϕn(1) and (a.)n=an=f(n)=f(x)|x=n.

Then k=0ϕk(x)tk=11ϕ.(x)t=exn=011ntxnn! =\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}.

Tom Copeland
  • 9,937