I am struggling on solving the inequality related to the group action and Bell numbers.
Let $G$ be a finite group acting on a set $X$ with $m$ elements. Prove that for each $1 \leq r \leq m$, $$\frac{1}{ \lvert G \rvert}\sum_{g \in G} \lvert F_g \rvert^r \geq B_r$$ where $F_g$ is the fix of $g \in G$ (the set of elements in $X$ which are fixed under the action of $g$)and $B_r$ is the Bell number of order $r$.
I have studied Burnside Lemma (which has the similar form with the lhs of the given inequality) so I tried to use the approach when proving it, but I am stuck because of the $r$-power in the summand. I also thought of giving appropriate surjection from the collection of fixes and the collection of every partition on an $m$-set, but it doesn’t look like a good approach.
It will be glad if anyone share me an insight on this problem.
Best Answer
(I) Burnside's lemma says, of course, the number of orbits of an action $G\curvearrowright\Omega$ is the average number of fixed points, or $|\Omega/G|=\frac{1}{|G|}\sum_{g\in G}|\Omega^g|$.
(II) If $G\curvearrowright\Omega$ then $G\curvearrowright\Omega^r$ componentwise, $g(\omega_1,\cdots,\omega_r):=(g\omega_1,\cdots,g\omega_r)$. Then $(\Omega^r)^g=(\Omega^g)^r$ (given a $g\in G$, a tuple is fixed iff each of its components is fixed).
(III) If $H\le G$ is a subgroup then $|\Omega/H|\ge|\Omega/G|$. In other words, quotienting by something bigger generally gives you something smaller (or equal).
Note if $G\curvearrowright\Omega$ then we can replace $G$ with its image in $S_\Omega$ without affecting the number of orbits. And its image is a subgroup of $S_\Omega$. So we can say $|\Omega^r/G|\ge|\Omega^r/ S_\Omega|\ge B_r$.
The last inequality can be explained as follows. For every partition $\Gamma$ of $\{1,\cdots,r\}$, we can define the subset $\Omega_\Gamma\subseteq\Omega^r$ as all $(\omega_1,\cdots,\omega_r)$ with $\omega_i=\omega_j$ iff $i,j$ are in the same part of $\Gamma$. If $|\Omega|<r$ then many of these $\Omega_\Gamma$s will be empty, but otherwise they are orbits of the action $S_\Omega\curvearrowright\Omega^r$.