4
$\begingroup$

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$."

$\endgroup$
2
  • 3
    $\begingroup$ That conjecture is very far off. Do you mean ordinary partitions instead of set partitions? The asymptotics are known for both. $\endgroup$ – Douglas Zare Mar 4 '10 at 15:05
  • $\begingroup$ The conjecture is true for ordinary partitions of integers. $\endgroup$ – Michael Lugo Mar 4 '10 at 15:44
8
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The sequence $C(n)=2^n$ satisfies $C(n)C(n+2)/C^2(n+1)$=1, but this tells us little about $C(n-1)/C(n)$. $\endgroup$ – Gerry Myerson Dec 10 '19 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.