Guichard-Combinatorics-Graph-Theory · Problem 3.2.5

Generating Functions

Mathematics — Probability · exponential-generating-functions-bell-numbers

Problem

Recall from section 1.4 that the Bell numbers BnB_n count all of the partitions of {1,2,…,n}\{1, 2, \ldots, n\}. Let f(x)=∑n=0∞Bn⋅xnn!f(x) = \sum_{n=0}^{\infty} B_n \cdot \frac{x^n}{n!}, and note that f′(x)=∑n=1∞Bnxn−1(n−1)!=∑n=0∞Bn+1xnn!=∑n=0∞(∑k=0n(nk)Bn−k)xnn!,f'(x) = \sum_{n=1}^{\infty} B_n \frac{x^{n-1}}{(n-1)!} = \sum_{n=0}^{\infty} B_{n+1} \frac{x^n}{n!} = \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} \binom{n}{k} B_{n-k}\right) \frac{x^n}{n!}, using the recurrence relation 1.4.1 for Bn+1B_{n+1} from section 1.4. Now it is possible to write this as a product of two infinite series: f′(x)=(∑n=0∞Bn⋅xnn!)(∑n=0∞anxn)=f(x)g(x).f'(x) = \left(\sum_{n=0}^{\infty} B_n \cdot \frac{x^n}{n!}\right)\left(\sum_{n=0}^{\infty} a_n x^n\right) = f(x)g(x). Find an expression for ana_n that makes this true, which will tell you what g(x)g(x) is, then solve the differential equation for f(x)f(x), the exponential generating function for the Bell numbers. From section 1.4, the first few Bell numbers are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437. You can use Sage to check your answer.

Related theory

Browse the problem library