Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
3  
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
add comment

1 Answer

up vote 5 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|improve this answer
add comment

Your Answer

 
discard

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.