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 infinity.

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.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s