In a party there are $n$ individuals. Each of them gives a present in the party. At the end of the party the presents are distributed randomly to each participant. How many individuals receive in average their own presents?
We want to solve the problem from the perspective of a particular group action $f: G \times M \rightarrow M$ and a fixed set, $M^g = \{ x \in M\mid g\cdot x = x \}$. I do not know how to go from here.
Do you have any suggestion or a solution proposal? Thanks.
All this boils down to is a shuffling of the presents, and the question how many fixed points.
We have $S_n$ acting on $n$ points.
By Burnside's lemma, $$\lvert M/G\rvert =1/\lvert G\rvert \sum \vert M^g\rvert. $$ The number of orbits is the average number of fixed points.
We get $$\lvert M/G\rvert =1,$$ because, as we know, the action is transitive.
$$, it should be ,$$.
$\endgroup$
I will here take the detour of walking through matrix representations of groups. If you have not studied linear algebra and matrices, this answer may not be so useful.
The group which describes the text is a permutation group.
The group action can in this case be defined in terms of the trace on the trivial matrix representation of the group -- the set of permutation matrices $\bf A$ of size $n\times n$ (where the group operation corresponds to matrix multiplication).
$$Tr({\bf A}) = \sum_{i=1}^n {\bf A}_{ii}$$
Now remember that each matrix $\bf A$ represents one particular permutation. One particular table of present-givings if you will. As we are interested in the average over all permutations, we are not finished yet, but now we want to calculate the expected value over all such $\bf A$ in our representation.
Can we prove somehow, for example by symmetry that the average representation matrix will be the $n\times n$ matrix filled with $1/n$ values everywhere, then we will have confirmed the result in Karl's comment above due to the linearity of trace and the expectation operators allows them to change place.
