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$