2
$\begingroup$

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.

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

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

$\endgroup$
4
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.