Let $G$ be a finite group acting on a finite set $X$. Define the permutation representation $(\rho, \mathbb{C}[X])$ of $G$ and compute its character $\pi_{X}$. Prove that $\left\langle\pi_{X}, 1_{G}\right\rangle_{G}$ equals the number of orbits of $G$ on $X$. If $G$ acts also on the finite set $Y$, with character $\pi_{Y}$, show that $\left\langle\pi_{X}, \pi_{Y}\right\rangle_{G}$ equals the number of orbits of $G$ on $X \times Y$.

Now let $G$ be the symmetric group $S_{n}$ acting naturally on the set $X=\{1, \ldots, n\}$, and let $X_{r}$ be the set of all $r$-element subsets of $X$. Let $\pi_{r}$ be the permutation character of $G$ on $X_{r}$. Prove that

$$\left\langle\pi_{k}, \pi_{\ell}\right\rangle_{G}=\ell+1 \text { for } 0 \leqslant \ell \leqslant k \leqslant n / 2$$

Deduce that the class functions

$$\chi_{r}=\pi_{r}-\pi_{r-1}$$

are irreducible characters of $S_{n}$, for $1 \leqslant r \leqslant n / 2$.