## Cute Combinatorial Problem

This was question 9 in the Sydney University Mathematical Society Problem Competition 2012. My solution was quite different to the model solution — I use a decomposition technique common in graph theory and algorithm runtime analysis.

### Problem:

For a permutation $\sigma$ of $\{1,2,3,\cdots,n\}$, a break of $\sigma$ is an element $k$ of $\{1,2,3,\cdots,n\}$ such that $\sigma(\{1,2,3,\cdots,k\})=\{1,2,3,\cdots,n\}$. The score of $\sigma$ is the square of the number of breaks. Show that the average score of all permutations of $\{1,2,3,\cdots,n\}$ tends to 0 as $n$ tends to inﬁnity.

### Solution:

First, note that

$\begin{array}{rcl} \displaystyle\sum_{j=1}^{n-1}{n \choose i}^{-1} & = & \displaystyle\frac{2}{n}+\sum_{j=2}^{n-2}{n \choose i}^{-1}\\ & \le & \displaystyle\frac{2}{n}+(n-3){n \choose 2}^{-1}\\ & = & \displaystyle\frac{2}{n}+\frac{2\left(n-3\right)}{n\left(n-1\right)}\\ & \rightarrow & \displaystyle0\mbox{ as }n\rightarrow\infty.\end{array}$

As a corollary, we can find ${M}$ so that

$\displaystyle \sum_{j=1}^{n-1}{n \choose i}^{-1}\le M$

for all ${n}$.

Now, let ${\sigma}$ vary uniformly at random in ${S_{n}}$ and let ${q(i,\sigma)}$ be an indicator function that is 1 if ${i}$ is a break of ${\sigma}$, and 0 otherwise. We note that ${i}$ and ${j}$ are breaks of ${\sigma}$ if and only if ${\sigma}$ is a permutation when restricted to ${\left\{ 1,\dots,i\right\} }$, ${\left\{ i+1,\dots,j\right\} }$ and ${\left\{ i+1,\dots,n\right\} }$. This says:

$\displaystyle \mathbb{E}\left[q(i,\sigma)q(j,\sigma)\right]=\mbox{Pr}\left(i\mbox{ and }j\mbox{ are breaks of \ensuremath{\sigma}}\right)=\frac{i!\left(j-i\right)!\left(n-j\right)!}{n!}.$

Then, by the linearity of expectation:

$\begin{array}{rcl} \displaystyle\mathbb{E}\left[\mbox{score}\left(\sigma\right)\right] & = & \displaystyle\mathbb{E}\left[\left(\sum_{i=1}^{n-1}q\left(i,\sigma\right)\right)^{2}\right]\\ & = & \displaystyle\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}\mathbb{E}\left[q(i,\sigma)q(j,\sigma)\right]\\ & \le & \displaystyle 2\sum_{j=1}^{n-1}\sum_{j=i}^{n-1}\mathbb{E}\left[q(i,\sigma)q(j,\sigma)\right]\\ & = & \displaystyle 2\sum_{j=1}^{n-1}\sum_{j=i}^{n-1}\frac{i!\left(j-i\right)!\left(n-j\right)!}{n!}\\ & = & \displaystyle 2\sum_{j=1}^{n-1}{n \choose i}^{-1}\sum_{j=i}^{n-1}{n-j \choose j-i}^{-1}\\ & = & \displaystyle 2\sum_{j=1}^{n-1}{n \choose i}^{-1}\left(1+\sum_{q=1}^{n-i-1}{n-i \choose q}^{-1}\right)\\ & \le & \displaystyle 2\left(M+1\right)\sum_{j=1}^{n-1}{n \choose i}^{-1}\\ & \rightarrow & \displaystyle 0\mbox{ as }n\rightarrow\infty \end{array}$

and the squeeze theorem yields the required result.