Home » Combinatorics » Burnside’s lemma and Bell numbers

# 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.