Burnside’s lemma and Bell numbers

In this post I am going to show that {B_n}, the {n}th Bell number, is larger than {n^n/n!}.

Our main tool will be Burnside’s lemma, which states that if a finite group {G} acts on a finite set {S}, the average number of fixed points of the elements of {G} is equal to the number of orbits of the action of {G} on {S}:

\displaystyle |G\backslash S|=\frac{1}{|G|}\sum_{g \in G}|\text{Fix }g|,

where {\text{Fix }g} is the set of fixed points of {g}.

We let {S_n}, the symmetric group on {n} letters, act on {\{1,2,\dots,n\}^n} component-wise. The elements of {[n]=\{1,2,\dots,n\}^n} are {n}-tuples consisting of integers between {1} and {n}. Now you may easily convince yourself that it is possible to send a tuple {(a_1, \dots, a_n)} to a tuple {(b_1, \dots, b_n)} if and only if whenever {a_i=a_j}, we also have {b_i=b_j}, and vice versa. In other words we view each {n}-tuple {(a_1, \dots, a_n)} as a function {\sigma: [n] \rightarrow [n]}; its fibres partition {[n]}, and composition with a permutation preserves the fibres of {\sigma}. It is immediate that {\sigma} and {\sigma'} are in the same orbit of {S_n} if and only if they have the same collection of fibres. For instance, (1,1,2) can be sent to (3,3,1) by the cycle (1\: 3\: 2) but there is no way to send (1,1,2) to (1,2,3), because any permutation will send (1,1,2) to a 3-tuple of the form (\bullet,\bullet,\circ).

Thus {S_n} has {B_n} orbits on {\{1,2,\dots,n\}^n}. On the other hand since our permutations act component-wise, we have

\displaystyle \text{Fix }_{[n]^n}g \cong (\text{Fix }_{[n]}g)^n,

i.e. the fixed points of {g} acting on {[n]^n} are the tuples {(a_1, \dots, a_n)} consisting of fixed points of {g} acting on {[n]}. Therefore, by Burnside’s lemma, we have

\displaystyle \frac{1}{n!}\sum_{g\in S_n} (\text{Fix }g)^n = B_n.

In fact the same argument shows that for any m\geq n, we have

\displaystyle \frac{1}{m!}\sum_{g\in S_m} (\text{Fix }g)^n = B_n.

In particular, the identity of {S_n} fixes all of {[n]}, so we have

\displaystyle \frac{n^n}{n!} \leq B_n.

In fact, by using the fact that a permutation of {[n]} consists of a subset of {[n]} (the subset of fixed points), and a derangement of the remaining elements, we easily obtain the formula

\displaystyle B_n = \frac{1}{n!}\sum_{i=0}^n {n \choose i} !(n-i) i^n

where {!n} is the number of derangements of a set of {n} elements.