# How orbits of $G$-sets and these characters are related

I've been learning about induced representations recently and I've come across something which I'm very confused about;

For any $$G$$-set $$X$$, the number of orbits is equal to $$(1_G, \chi_{\mathbb{C}[X]})$$ where $$1_G$$ denotes the character of the trivial representation and $$\chi_{\mathbb{C}[X]}$$ denotes the character of the permutation representation defined below;

$$\mathbb{C}[X]$$ is the natural permutation representation with basis $${\{e_x : x \in X}\}$$ and the action of $$g$$ being $$ge_{x} = e_{gx}$$.

I have no idea why this is true. I know that $$Ind_{H}^{G} \mathbb{C} \simeq \mathbb{C}[G/H]$$ and the explanation I've seen goes like this;

If $$X$$ is transitive, then $$(1_G, \chi_{\mathbb{C}[X]}) = 1$$, which can be shown through Frobenius Reciprocity. If $$X$$ isn't transitive, then $$X = \bigcup_{i=1}^{n} X_i$$ where the $$X_i$$ are transitive. Then, $$(1_G, \chi_{\mathbb{C}[X]}) = (1_G, \chi_{\mathbb{C}[X_1] \oplus \cdots \oplus \mathbb{C}[X_n]})= (1_G, \chi_{\mathbb{C}[X_1]}) + ... + (1_G, \chi_{\mathbb{C}[X_n]}) = n$$.

I mean, I understand every line of the proof and can follow it, but why does the value $$(1_G, \chi_{\mathbb{C}[X]})$$ give you the number of orbits of a $$G$$-set? What does this value have to do with orbits of $$G$$-sets?

The inner product $$(1_G,\chi_{\mathbb{C}[X]})$$ is just the dimension of the space of intertwining maps from the trivial representation $$\mathbb{C}$$ to $$\mathbb{C}[X]$$. A linear map $$T:\mathbb{C}\to\mathbb{C}[X]$$ is determined by $$T(1)$$, and is intertwining iff $$T(1)$$ is fixed by every element of $$G$$. So, $$(1_G,\chi_{\mathbb{C}[X]})$$ is just the dimension of the space of vectors in $$\mathbb{C}[X]$$ which are fixed by every element of $$G$$.

Now, when is an element $$\sum c_xe_x\in\mathbb{C}[X]$$ fixed by every element of $$G$$? Exactly when the coefficients $$c_x$$ are constant on each orbit (since the action of $$G$$ just permutes these coefficients transitively within each orbit). Letting $$X_1,\dots,X_n$$ be the orbits, this means that the vectors $$v_i=\sum_{x\in X_i} e_x$$ are a basis for the space of vectors fixed by $$G$$, and in particular that space has dimension $$n$$.

I really like Eric Wofsey's answer (+1), which was posted as I was writing this. However, this is a different solution, so I'll post it too.

My solution follows from the orbit-stabilizer theorem.


Then $$(1_G,\chi_{\CC[X]}) = \frac{1}{|G|}\sum_{g\in G} \chi_{\CC[X]}(g) =\frac{1}{|G|}\sum_{g\in G}\sum_{x\in X} [gx=x],$$ i.e. the inner product is the average number of elements of $$X$$ fixed. Rearranging the sums, we have $$(1_G,\chi_{\CC[X]})=\frac{1}{|G|}\sum_{x\in X} \sum_{g\in G}[gx=x] = \frac{1}{|G|} \sum_{x\in X} |\operatorname{Stab}(x)|.$$ Now pull the cardinality of the group in, and recognize the term in the summation as the index of the stabilizer $$(1_G,\chi_{\CC[X]})=\sum_{x\in X} \frac{|\newcommand\Stab{\operatorname{Stab}}\Stab(x)|}{|G|}=\sum_{x\in X}\frac{1}{[G:\Stab(x)]},$$ but the index of the stabilizer equals the size of the orbit, so we have $$(1_G,\chi_{\CC[X]})=\sum_{x\in X} \frac{1}{|Gx|} =\sum_{\text{orbits}} 1 =\#\{\text{orbits}\}$$

A note on notation

For a statement $$P$$, I use the notation $$[P]:=\begin{cases} 1 & \text{ P is true} \\ 0 & \text{otherwise}.\end{cases}$$

Note

Also this result is essentially just Burnside's lemma (modulo my comment on the character counting the number of fixed points).