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.

• This also appeared at the following MSE link. – Marko Riedel Mar 20 '17 at 21:38

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}

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 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$