What are the examples of interesting combinatorial identities (e.g. bijection between two sets of combinatorial objects) that can be proved using representation theory, or has some representation theoretic interpretation. Please also mention whether a purely combinatorial proof is known in each case.
[Math] Applications of Representation Theory in Combinatorics
algebraic-combinatoricsbig-listco.combinatoricsrt.representation-theory
Related Solutions
Here is a fact that I find interesting. Strictly speaking it is to say that a certain number counts three completely unrelated things, but it seems easy to make these into a combinatorial problem or to define an explicit bijection between two (or three) sets.
So, the concrete example is $168$, which
(1) the number of hours in a week;
(2) the number of primes under $1000$; and
(3) the size of the smallest simple group of Lie type.
$168$ is also $4 \times 42$, where $42$ is that famous number Douglas Adams wrote about. (How did he know?) Which is of course the reciprocal of the smallest positive number that can be written as $$1-\frac 1a -\frac 1b -\frac 1c$$ with $a,b,c\in \mathbb N$ and coincidentally (and relatedly) the largest size of the automorphism group of $C$ a smooth projective curve of genus at least $2$ is $42\cdot {\rm deg} K_C$ and of $S$ a smooth projective surface of general type is $(42 K_S)^2$.
So I guess one could add that $168$ is also
(4) the maximum value of $\frac 4{1 -\frac 1a -\frac 1b -\frac 1c}$ with $a,b,c\in \mathbb N$; and
(5) the largest possible size of the automorphism group of a smooth complex projective curve of genus $3$,
but I admit the last two are a little artificial...
This is an interesting question, even though it is not well defined. Call a group "good" if it has a "good" bijection between its conjugacy classes and its irreducible complex representations. I agree with Alexander that the definition of a "good" bijection/group should be guided by classes of examples, but I prefer that a class of bijections/groups should be infinite.
There are families of good metacyclic groups. For example, if $n=2m+1$ is an odd integer, then the dihedral groups $D_{2n}=\langle a,b\mid a^2=b^n=1,\; a^{-1}ba=b^{-1}\rangle$ of order $2n$ are good. The conjugacy classes $\{b^j,b^{-j}\}$, $1\leq j\leq m$, $\{1\}$, and $\{a,ab,ab^2,\dots,ab^{n-1}\}$ correspond bijectively (I believe this is "good") to the irreducible representations $\rho_j$, $1\leq j\leq m$, $\sigma_0$, and $\sigma_1$, respectively where $\rho_j(a)=\begin{pmatrix}0&1\\1&0\end{pmatrix}$, $\rho_j(b)=\begin{pmatrix}\zeta_n^j&0\\0&\zeta_n^{-j}\end{pmatrix}$, $\sigma_k(a)=\begin{pmatrix}(-1)^k\end{pmatrix}$, $\sigma_k(b)=\begin{pmatrix}1\end{pmatrix}$ and $\zeta_n=e^{2\pi i/n}$.
If an infinite family $G_1, G_2,\dots$ of groups is good, then you know a vast amount about each $G_n$ and can likely produce is a formula writing $|G_n|$ as a sum of the squares of the degrees of the irreducible representations. For $D_{2n}$ this is $2n=4m+2=m\times 2^2+2\times 1^2$. If $G_n$ is an extraspecial group of (odd) order $p^{1+2n}$ and exponent $p$, then the formula is $p^{1+2n}=(p-1)\times(p^n)^2+p^{2n}\times 1^2$. Perhaps the existence of such a formula should be part of the elusive definition of "good".
Addition: Yes Alexander, you are correct, the extraspecial groups $G_n$ of order $p^{1+2n}$ and odd exponent $p$ are "good". To describe a "good" bijection I need some notation. Let $f_n\colon V\times V\to\mathbb{F}_p$ be a nondegenerate symplectic form on $V=\mathbb{F}_p^{2n}$. Multiplication in $G_n=V\times \mathbb{F}_p$ is given by $(v_1,\lambda_1)(v_2,\lambda_2)=(v_1+v_2,\lambda_1+\lambda_2+{\frac12}f_n(v_1,v_2))$, or by the matrices you indicate. The conjugacy classes are as follows: the $p$ one-element (central) classes $Z_\lambda:=\{(0,\lambda)\}$, $\lambda\in\mathbb{F}_p$, and the $p^{2n}-1$ classes $C_v:=\{(v,\lambda)\mid \lambda\in\mathbb{F}_p\}$ where $0\neq v\in V$. The irreducible representations are also easy. The trivial degree-1 representation corresponds to class $Z_0$ containing the identity element. The $p^{2n}-1$ nontrivial degree-1 representations correspond to the $p$-element classes $C_v$. The remaining $p-1$ irreducibles of degree $p^n$ correspond to the $p-1$ central conjugacy classes $Z_\lambda$, with $0\neq\lambda\in\mathbb{F}_p$. Fix a maximal totally isotropic subspace $W$ of $V$. By Witt's theorem $|W|=p^n$. Then $A:=W\times\mathbb{F}_p$ is a maximal abelian subgroup of $G_n$ of index $p^n$. Let $\sigma_\lambda$ be the 1-dimensional representation of $A$, with kernel $W$, mapping $(0,1)$ to $e^{2\pi i\lambda/p}$. The induced representations $\rho_\lambda={\rm Ind}_A^{G_n}(\sigma_\lambda)$ are irreducible of degree $p^n$. (A direct calculation shows $\langle\rho_\lambda,\rho_\lambda\rangle=1$. Choosing a different $f_n$, or a different maximal totally isotropic subspace $W'$, gives equivalent representations $\rho'_\lambda$. The $W$s are permuted by ${\rm Aut}(G_n)$.) This is a "good" bijection, as identifying $V$ with its dual seems allowed.
Best Answer
It is unclear exactly what is meant by a "combinatorial identity." For instance, let $X_n$ denote the set of alternating permutations in the symmetric group $\mathfrak{S}_n$ that are also cycles of length $n$. Then $$ \#X_n = \frac 1n\sum_{d|n}\mu(d)(-1)^{(d-1)/2}E_{n/d}, $$ where $E_{n/d}$ is an Euler number. Assuming that this counts as a combinatorial identity, then there are many further results of this nature at http://math.mit.edu/~rstan/papers/altenum.pdf. The only known proofs of most of them (including the one above, even when $n$ is prime) use the representation theory of the symmetric group.
Another identity which has no combinatorial proof is $$ \frac{1}{n!}\sum_{u,v\in\mathfrak{S}_n} q^{\kappa(uvu^{-1}v^{-1})} = \sum_{\lambda\vdash n}\prod_{t\in\lambda} (q+c(t)), $$ where $\kappa(w)$ is the number of cycles of $w$, and $c(t)$ is the content of the square $t$ of (the diagram of) $\lambda$. This is Exercise 7.68(e) of my book Enumerative Combinatorics, vol. 2. Many other similar results appear near this exercise.