Proving Average Fixed Points of a Permutation on n Letter is 1 I'm in a combinatorics reading group and I was asked to prove that the average number of fixed points in a permutation on $n$ letters is $1$. I was also told to use the expansion for $log(1-x)$ and the equation $$\sum_{n \ge 0}\frac{t^{n}}{n!}A_{n}(x) = e^{tx + \sum_{n \ge 2}\frac{t^{k}}{k}}$$ where $A_{n}(x) = \sum_{w \in S_{n}}x^{fp(w)}$, $S_{n}$ is the set of all permutations on $n$ letters, and $fp(w)$ is the number of fixed points in a permutation. 
My Attempt:
I decided to find the generating functions for the sum of all fixed points in $S_{n}$ and $|S_{n}|$. To my understanding these should be the same function so multiplying one by the other's reciprocal should yield $1$. The generating function for the sum of all fixed points in $S_{n}$ is $A_{n}(x)$ so I'm finished there. In my attempt to find a generating functions for $|S_{n}|$ I considered some letter $k$ in $w$. There are $f(n-1)$ ways to chose the order of the other letters and there are $n$ ways to chose the $k$ letter so $f(n) = nf(n-1)$. I then shifted the recurrence to $f(n+1) = (n+1)f(n)$ and used the generating function $F(x) = \sum_{n \ge 0}\frac{f(n)x^{n}}{n!}$ to obtain the differential equation $F' = xF' + F$. But with the convention $F(0) = 1$, $F = \frac{1}{1-x}$. This is where I could use some guidance because the coefficients of my recurrence shouldn't $1,1,\ldots$. 
P.S. I'm aware I haven't used any of the suggested equations yet either. This leads me to think my solution is moving in the wrong direction.
 A: A much easier hint than the one given and easier method than the one the original hint is alluding to is to recognize that expectation is a linear function.
Given a random permutation $\pi$, let $X_i$ be the indicator random variable such that $X_i=\begin{cases}1&\text{if}~i=\pi(i)\\ 0&\text{otherwise}\end{cases}$
The random variable describing the total number of fixed points is then $X=\sum\limits_{i=1}^n X_i$
By linearity of expectation then, we have $E[X]=E[\sum\limits_{i=1}^n X_i] = \sum\limits_{i=1}^n E[X_i]$
What is the probability that a randomly chosen permutation fixes the $i$'th number (or letter if you insist, whatever set the permutation is acting on)?

 There are $n!$ permutations on $n$ characters.  $(n-1)!$ of which fix the $i$ 'th character.  The probability then that the $i$ 'th character is fixed is $\frac{(n-1)!}{n!}=\frac{1}{n}$

Computing the summation then

 $E[X]=\sum\limits_{i=1}^nE[X_i] = \sum\limits_{i=1}^n \frac{1}{n}=n\cdot \frac{1}{n}=1$

A: Preamble
The mixed generating function for permutations length $n$ with $r$ cycles is
$$\exp\left(y\sum_{k\ge 1}\frac{t^k}{k}\right)$$
hence the coefficient of $y^rt^n/n!$ is the number of permutations of $n$ elements with $r$ cycles. 
$y$ is the enumerator for number of cycles and $t$ is the enumerator for number of permutation elements (i.e. permutation length). 
The function essentially says that each cycle (enumerator $y$) will have $1,2,3\ldots$ elements in it (represented by the element number enumerator in $t^1/1, t^2/2, t^3/3,\ldots$). So the term $t^1/1$ will count the numbe of cycles of length $1$, i.e. our fixed points. 
In order for us to count number of fixed points in a permutation we must attach an enumerator $x$ to $t^1/1$ and since we are interested only in total permutations length $n$  and not in cycle length we can set $y=1$ and we get
$$\exp\left(tx+\sum_{k\ge 2}\frac{t^k}{k}\right)=\sum_{n\ge 1} A_n(x)\frac{t^n}{n!}$$
in other words $A_n(x)$ has a contribution for every cycle of length $1$ (fixed point) in permutations of length $n$. $A_n(x)$ will also contain constant terms arising from those permutations with no fixed points (i.e. with cycles length $2,3,4,\ldots$ etc) this means that
$$\begin{align}A_n(x)&=\sum_{w\in S_n}x^{fp(w)}\\
&=\sum_{a=0}^{n} \left(\text{# of length $n$ permutations with $a$ fixed points}\right)x^a
\end{align}$$

Answer
Anyway, when you are asked for the "arithmetic mean" or "expectation" of a quantity and you have it's generating function just remember differentiate with respect to the enumerator of said quantity, in this case, by $x$
$$D_x\left(\exp\left(tx+\sum_{k\ge 2}\frac{t^k}{k}\right)\right)=D_x\left(\sum_{n\ge 1} A_n(x)\frac{t^n}{n!}\right)$$
$$\implies t\exp\left(tx+\sum_{k\ge 2}\frac{t^k}{k}\right)=\sum_{n\ge 1} D_x\left(\frac{A_n(x)}{n!}\right)t^n\tag{1}\label{1}$$
Notice that 
$$D_x\left(\frac{A_n(x)}{n!}\right)=\frac{1}{n!}\sum_{a=0}^{n} \left(\text{# of length $n$ permutations with $a$ fixed points}\right)\cdot a\cdot x^{a-1}\tag{2}\label{2}$$
so if we set $x=1$ then the right hand side of $\eqref{2}$ is the expectation of the number of fixed points for permutations length $n$: $E(n)$. So setting $x=1$ on both sides of $\eqref{1}$ gives
$$t\exp\left(\sum_{k\ge 1}\frac{t^k}{k}\right)=\sum_{n\ge 1}E(n)t^n$$
then remember the expansion
$$\log(1-t)=-\sum_{k\ge 1}\frac{t^k}{k}$$
therefore
$$t\exp\left(-\log(1-t)\right)= \sum_{n\ge 1}E(n)t^n$$
$$\implies t(1-t)^{-1}=\sum_{n\ge 1}E(n)t^n$$
$$\implies \sum_{n\ge 1}t^n=\sum_{n\ge 1}E(n)t^n$$
equating coefficients of $t^n$
$$E(n)=1$$
A: This is (I think) the simplest of ways to show that the average is 1: Consider the set of permutations and the set of fixations, where a fixation is the pair formed by a permutation and a fixed point of it. For instance, 32541 and 32541 are the two different fixations for the permutation 32541. Then (for any fixed $n$ rather than 5) the number of fixations is the number of permutations, because the following maps are clearly inverse bijections:

*

*Given a permutation, move the last element to its place to get a fixation (for instance, 14253 applies to 14325).

*For any fixation, move the fixed number to the last place.

