Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following inequality came up while trying to resolve a conjecture about a certain class of partitions (the context is not particularly enlightening): $$ B_n^2 \leq B_{n-1}B_{n+1} $$ for $n \geq 1$, where $B_n$ denotes the $n$th Bell number (i.e. the number of partitions of an $n$-element set). I ran this inequality through Maple for values of $n$ up to 500 or so and did not find a counterexample.

There is no nice closed form for $B_n$, so I was hoping to prove this inequality combinatorially rather than analytically (particularly since the given inequality is just the simplest version of a more general inequality I hope to establish).

Let $P_n$ be the collection of (not number of) all partitions of an $n$-element set. My approach was to find an injection from $P_n \times P_n$ into $P_{n-1} \times P_{n+1}$. Suppose we are to map $(C_1, D_1)$ to $(C_2, D_2)$ and suppose, for convenience, our ground set is the integers from $1$ to $n$.

A natural seeming choice was to choose $C_2$ to be the partition $C_1$ with the element $n$ removed. Since removing $n$ will map many partitions in $P_n$ to the same partition in $P_{n-1}$, we would need somehow to choose $D_2$ in such a way as to retain information about where $n$ was in $C_1$. We have the new element $n+1$ to work with, so perhaps it can be used to "tag" the partitions in some unique way.

I've stressed a combinatorial approach in this post, but I would greatly appreciate any techniques that might be of use in establishing (or refuting) this inequality.

share|improve this question
5  
A sequence $c_n$ satisfying $c_n^2 \le c_{n-1} c_{n+1}$ for all $n$ is called discrete log-convex, for what it's worth. –  Sasha Sep 27 '11 at 19:32

3 Answers 3

up vote 16 down vote accepted

This answer is courtesy of Bouroubi (paraphrased):

Theorem. Define $B(x)=e^{-1}\sum_{k=0}^\infty k^x k!^{-1}$. Dobinski's formula states $B(n)=B_n$ is the $n$th Bell number. Now we let $\frac{1}{p}+\frac{1}{q}=1$. Then $$B(x+y)\le B(px)^{1/p}B(qx)^{1/q}.$$ Proof. Let $Z$ be the discrete random variable with density function (under counting measure) $$P(Z=k)=\frac{1}{e}\frac{1}{k!}.$$ Observe $\mathbb{E}(Z^x)=B(x)$. Hölder's inequality gives $\mathbb{E}(Z^{x+y})\le\mathbb{E}(Z^{px})^{1/p}\mathbb{E}(Z^{qx})^{1/q}$, which proves the theorem.

Corollary. The sequence $B_n$ is logarithmically convex, or equivalently $$B_n^2\le B_{n-1}B_{n+1}.$$ Proof. Set $x=\frac{n-1}{2}$, $y=\frac{n+1}{2}$, and $p=q=2$ in the original theorem.

Not a combinatorial proof, but straightforward given a couple powerful premises at least. I'm curious, what's the general formula you're trying to establish?

share|improve this answer
    
(+1) Very nice proof, and thanks for the reference. –  Sasha Sep 27 '11 at 19:44
    
"Probability mass function", or "probability density function with respect to counting measure", or just "probability distribution", would be a term less likely to be misunderstood than "probability distribution function", because of the convention of using that latter term to refer to the cumulative distibution function. –  Michael Hardy Sep 27 '11 at 20:18
    
@Michael: Right, right. I was going to change that term from the reference but spaced off. –  anon Sep 27 '11 at 20:24
    
I have a suspicion that finding an injection of the sort proposed in the question is possible, and I wonder wheter, in the case where $x$ and $y$ and $ps$ and $py$ are integers, the same thing could be done in order to prove the inequality $B(x+y)\le B(px)^{1/p}B(qx)^{1/q}$. –  Michael Hardy Sep 27 '11 at 20:24
    
@Michael: I'm still looking for an injection proof, but I'm unsure if the idea is powerful enough to prove that generalized inequality. –  anon Sep 27 '11 at 20:43

Here's a combinatorial argument. Let $S_n$ denote the total number of sets over all partitions of $\{1, 2, \ldots, n\}$, so that $A_n = \frac{S_n}{B_n}$ is the average number of sets in a partition of $\{1, 2, \ldots, n\}$.

First, $A_n$ is increasing. Each partition of $\{1, 2, \ldots, n\}$ consisting of $k$ sets maps to $k$ partitions consisting of $k$ sets (if $n+1$ is placed in an already-existing set) and one partition consisting of $k+1$ sets (if $n+1$ is placed in a set by itself) out of the partitions of $\{1, 2, \ldots, n+1\}$. Thus partitions with more sets reproduce more partitions of their size as well as one larger partition, raising the average number of sets as you move from $n$ elements to $n+1$ elements.

Next, the inequality to be proved is equivalent to the fact that $A_n$ is increasing. Separate the partitions counted by $B_{n+1}$ into (1) those that have a set consisting of the single element $n+1$ and (2) those that don't. It should be clear that there are $B_n$ of the former. Also, there are $S_n$ of the latter because each partition in group (2) is formed by adding $n+1$ to a set in a partition of $\{1, 2, \ldots, n\}$. Thus $B_{n+1} = B_n + S_n$.

The inequality to be shown can then be reformulated as $$\frac{B_{n+1}}{B_n} \geq \frac{B_n}{B_{n-1}} \Longleftrightarrow 1 + \frac{S_n}{B_n} \geq 1 + \frac{S_{n-1}}{B_{n-1}} \Longleftrightarrow A_n \geq A_{n-1},$$ and we know the last inequality holds because we've already shown that $A_n$ is increasing.

share|improve this answer

Some more references, which will give you some additional proofs if you're interested in tracking them down.

(Added: The Bender and Canfield paper mentioned below gives this bound as well.)

"The log-convexity of the Bell numbers was first obtained by Engel ["On the average rank of an element in a filter of the partition lattice," Journal of Combinatorial Theory Series A 65 (1994) 67-78] . Then Bender and Canfield ["Log-concavity and related properties of the cycle index polynomials," Journal of Combinatorial Theory Series A 74 (1996) 57-70] gave a proof by means of the exponential generating function of the Bell numbers. Another interesting proof is to use Dobinski formula [as in anon's answer]. We can also obtain the log-convexity of the Bell numbers by Proposition 2.3 and the well-known recurrence $$B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k."$$

Liu and Wang's proposition 2.3 (due to Davenport and Pólya) says

If $\{x_n\}$ is log-convex, and $z_n = \sum_{k=0}^n \binom{n}{k} x_k$, then $\{z_n\}$ is log-convex as well.

While at first this may seem circular when applied to the Bell numbers, it's not. Proposition 2.3 says that if $x_{k-1}x_{k+1} \geq x_k^2$ for $1 \leq k \leq n-1$ then $z_{k-1}z_{k+1} \geq z_k^2$ for $1 \leq k \leq n-1$. With the Bell number recurrence, then, we have $B_{k-1}B_{k+1} \geq B_k^2$ for $1 \leq k \leq n-1$ implying $B_{k}B_{k+2} \geq B_{k+1}^2$ for $1 \leq k \leq n-1$. Since we can easily check that $B_0 B_2 \geq B_1^2$, this gives us an inductive proof of the log-convexity of the Bell numbers.

  • (Added 2) Canfield, in "Engel's inequality for Bell numbers" [Journal of Combinatorial Theory Series A 72 (1995) 184-187], discusses this inequality as well and gives the same proof as in my other answer.
share|improve this answer

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.