Sunday, 18 June 2006

co.combinatorics - On the Bell Numbers

It's easy to see that $B_n ge 2 B_{n-1}$ since we always have a choice of whether to add $n$ to the same part as $n-1$ or not. Since the number of parts in a typical set partition of size $n-1$ grows, the choices for adding $n$ to a new or existing part grow, so



$$lim_{ntoinfty} B_{n-1}/B_n = 0.$$
There are asymptotics in the Wikipedia article on the Bell numbers, but it may not be obvious how to work with the Lambert $W$-function in that expression, or how to bound $B_{n-1}/B_n$. A faster proof that the limit is $0$ can be obtained from Dobrinski's formula, that $B_n$ is the $n$th moment of a Poisson distribution with mean $1$:



For any $c in mathbb R$, the Poisson distribution has positive probability of being greater than $c$. So, for large enough $n$, the $n$th moment $B_n$ is at least $c^n$. By Jensen's inequality, the moments satisfy



$$B_n^{frac{n+1}{n}} le B_{n+1}$$



$$c le sqrt[n]{B_n} le frac {B_{n+1}}{B_n}$$

No comments:

Post a Comment