MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Edit (first version was incorrectly stated. Thank you Douglas and others for your corrections) Let $B_n$ be the $n$th Bell number (the number of partitions of a set with $n$ members). For each $n > 3$, I have a set $A_n$ of size $|A_n|=B_n$. I then have a subset $A'_n \subset A_n$ where $|A'_n|=B_n-B_{n-1}$. I would like to say something about the size of $A'_n$ relative to the size of $A_n$. For instance, it seems that $lim_{n \to \infty} \frac{B_{n-1}}{B_n}=0$. Can I make a stronger statement about the ratio of successive Bell numbers? How can I formalize the statement "for sufficiently large $n$, most of $A_n$ is in $A'_n$."

share|cite|improve this question
That conjecture is very far off. Do you mean ordinary partitions instead of set partitions? The asymptotics are known for both. – Douglas Zare Mar 4 '10 at 15:05
The conjecture is true for ordinary partitions of integers. – Michael Lugo Mar 4 '10 at 15:44
up vote 7 down vote accepted

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

share|cite|improve this answer

A precise estimate of the relative ratios of consecutive Bell numbers is proved by Asai, Nobuhiro; Kubo, Izumi; Kuo, Hui- Hsiung in Acta Appl. Math. 63 (2000), no. 1-3, 7987: $$1\leq \frac{B(n)B(n+2)}{B^2(n+1)}\leq \frac{n+2}{n+1}$$

share|cite|improve this answer

Your Answer


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.