Log-Convexity of the Bell Numbers

A sequence \{a_n\} is said to be log-convex if, for all n \geq 1, a_n^2 \leq a_{n-1} a_{n+1}.

In this post I give a short, combinatorial-flavored proof that the Bell numbers are log-convex.  The argument is from my answer here on Math.SE.

The combinatorial interpretation of the Bell number B_n is that it counts the number of ways to partition the set \{1, 2, \ldots, n\} into nonempty subsets.  Let S_n denote the total number of sets over all partitions of \{1, 2, \ldots, n\}.  Then A_n = S_n/B_n is the average number of sets in a random partition of \{1, 2, \ldots, n\}.

Claim 1: A_n is increasing.

Proof: Each partition of \{1, 2, \ldots, n+1\} can be associated with a partition of \{1, 2, \ldots, n\} by removing the element n+1 from the set containing it.  Under the inverse of this mapping, 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 of \{1, 2, \ldots, n\} with more sets map to more partitions of \{1, 2, \ldots, n+1\} containing the same number of sets as well as one partition with one more set.  This raises the average number of sets as you move from n elements to n+1 elements.

Claim 2: The log-convexity of B_n is equivalent to the fact that A_n is increasing.

Proof: 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.

Therefore,

\displaystyle B_n^2 \leq B_{n-1} B_{n+1} \iff \frac{B_{n+1}}{B_n} \geq \frac{B_n}{B_{n-1}} \iff 1 + \frac{S_n}{B_n} \geq 1 + \frac{S_{n-1}}{B_{n-1}} \iff A_n \geq A_{n-1}.

Since we established the last inequality in Claim 1, the Bell numbers are log-convex.


I was not the first to find this proof; Canfield [1] published it in 1995.  Engel [2] was the first to prove that the Bell numbers are log-convex; he used a different method.  See my answer here on Math.SE for references to more proofs.

References

1.  E. Rodney Canfield, “Engel’s Inequality for Bell Numbers,” Journal of Combinatorial Theory, Series A, 72 (1995) 184-187.

2. Konrad 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.

Advertisements
This entry was posted in Bell numbers, combinatorics, inequalities, sequences and series. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s