Skip to main content
MathOverflow

Return to Answer

corrected spelling
Source Link
John Baez
John Baez
  • 22.3k
  • 3
  • 85
  • 170

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_{n\to\infty} 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'sDobiński'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}$$

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_{n\to\infty} 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}$$

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_{n\to\infty} 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 Dobiński'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}$$

added 417 characters in body
Source Link
Douglas Zare
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

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_{n\to\infty} B_{n-1}/B_n = 0.$$ There are complicated 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, thanthat $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}$$

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_{n\to\infty} B_{n-1}/B_n = 0.$$ There are complicated asymptotics in the Wikipedia article on the Bell numbers. A faster proof that the limit is $0$ can be obtained from Dobrinski's formula, than $B_n$ is the $n$th moment of a Poisson distribution with mean $1$.

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_{n\to\infty} 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}$$

Source Link
Douglas Zare
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

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_{n\to\infty} B_{n-1}/B_n = 0.$$ There are complicated asymptotics in the Wikipedia article on the Bell numbers. A faster proof that the limit is $0$ can be obtained from Dobrinski's formula, than $B_n$ is the $n$th moment of a Poisson distribution with mean $1$.