Much as I like Burnside's Lemma, induced (permutation) representations, and other parts of group theory, I can't resist pointing out an alternative argument that uses essentially no group theory but relies on the fact that expectation (of random variables) is linear. Since $chi(g)$ is the number of fixed-points of $g$, its square is the number of fixed ordered pairs $(x,y)$, where of course fixing a pair means fixing both its components. So the $langlechi,chirangle$ in the question is the average number of fixed pairs of a permutation $g$, in other words the expectation (with respect to the uniform probability measure on $S_n$) of the random variable "number of fixed pairs." That random variable is the sum, over all pairs $(x,y)$, of the indicator variable $F_{x,y}$ whose value at any permutation $g$ is 1 or 0 according to whether $g$ fixes $x$ and $y$ or not. So $langlechi,chirangle$ is the sum, over all $x,y$, of the expectations of these $F_{x,y}$, and these expectations are just the probabilities that a random permutation fixes $x$ and $y$. For each of the $n$ pairs where $x=y$, that probability is $1/n$, so all these together contribute 1 to the sum. For each of the remaining $n^2-n$ pairs, the probability is $(1/n)(1/(n-1))$ (namely, probability $1/n$ to fix $x$ and conditional probability $1/(n-1)$ to fix $y$ given that $x$ is fixed). So these pairs also contribute 1 to the sum, for a total of 2.
No comments:
Post a Comment