My Journey Towards Emptiness!!: 09/01/2009

I started reading Knuth's Volume-4 series - you can get it here http://www.cs.utsa.edu/~wagner/knuth/. The chapter Introduction to Combinatorial Searching starts off with the analysis of some of the fundamental combinatorial objects such as Langford pairs. I came across an interesting exercise which asks to prove a statement on how to count these Langford pairs. I infact spend some time on this problem and finally the solution seemed extremely elegant. Before that let me quicky define what a Langford pair is.

Langford Pair: Given a multi set $S = \{1,1,2,2,3,3\ldots n,n\}$ of integers - every integer $1\leq i \leq n$ is repeated exactly twice. A Langford pair is a permutation $\pi$ of , with a property that there are exactly $i \in S$ elements between and its copy, $1\leq i \leq n$ . (e.g. for $L = \{ 3,1,2,1,3,2 \}$ , we can see that and its copy has exactly element between them. Also observe the property of and ) Having defined what a Langford pair is we now ask the question how can we count. The exercise I was talking about initially asks to prove the following.

Let denote all the possible Langford pairs which can be formed from set $S = \{1,1,2,2,3,3\ldots n,n\}$ .
Let $f(x_1,x_2,\ldots ,x_{2n}) = \displaystyle\Pi_{k=1}^{n}(x_kx_{n+k} \displaystyle\sum_{j=1}^{2n-k-1}x_jx_{j+k+1})$
Let $Y=\{-1,+1\}^{2n}$
Show that $\displaystyle\sum_{y \in Y}f(x_1,x_2,\ldots x_{2n}) = 2^{2n+1}L_n$

Looking at the problem first, I was a little unclear what is the intuition behind defining such a function (i.e. $f(x_1,\ldots x_{2n})$ ). After careful thought and analysis I understood that the function $f(x_1,\ldots x_{2n})$ was defined so cleverly that the total number of Langford pairs can be found algebraically. This quickly reminded me about the generating functions , where we use an algebraic expression to count possible partitions of a natural number. Let me first explain the intuition behind that algebraic formulation of function $f(x_1,x_2\ldots x_{2n})$ .

Consider a Langford permutation , now consider the positions of each integer $1\leq k \leq n$ occurs for the first time from the left of the permutation. By the definition of the Langford pair if an integer appears at position in the permutation, then none of the integers except can occur at position - which is towards the right. Also note that the integer can only occur at positions $1\leq j \leq 2n-k-1$ . Let $S=\{1,1,2,2,3,3,4,4,\}$ , for example, in any Langford permutation of , the integer can only occur at positions $1\leq j \leq 3$ . Similarly integer can occur at positions $1\leq j \leq 6$ . Now this explains the intuition behind $x_{j}x_{j+k+1}$ in the definition of the function $f(\dots)$ .
Let $P':\{1,2,3,\ldots n\}\rightarrow \{1,2,3,\ldots ,2n\}$ be a function - we call it a position map. Which maps every integer $1\leq k \leq n$ to a index/position in the permutation $1\leq j \leq 2n$ . Let $P_l = \{1,2,3,\ldots 2n\}$ and $P=\{P'(1),P'(1)+2,P'(2),P'(2)+3,\ldots,P'(n),P'(n)+n+1\}$ . We now see that a position map can generate a Langford permutation only if $\vert P_l\cap P\vert = 2n$ . In other words the position mapping function should map the integers $1\leq k \leq n$ in such a way that, when we introduce the corresponding pairs - at positions , we should not see any duplicates. Now all possible function mappings of is described algebraically as follows.

$\begin{displaymath} \begin{array}{l} t(x_1,x_2\ldots x_{2n})= \\ (x_1x_3 + x_2x... ... \ldots (x_1x_{n+2}+x_2x_{n+3}\ldots x_{n-1}x_{2n}) \end{array}\end{displaymath}$

Now if we observe carefully every term in the expansion of the above algebraic expression represents every possible (see above). More specifically every term in the above expansion is of the form $x_1^{a_1}x_2^{a_2}x_3^{a_3}\ldots x_{2n}^{a_{2n}}$ and $1\leq a_j \leq n, 1\leq j \leq 2n$ . Now we are looking for all the possible terms which have $a_j = 1 , 1\leq j \leq 2n$ , every such term represents a Langford pair.
We now have seen how a clever algebraic expression can help us in counting difficult combinatorial objects. But we are still not done - why? . Because we need to filter out all the terms which don't satisfy $a_j = 1 , 1\leq j \leq 2n$ . How do we do that ?, this is where the trick of odd , even functions come into play. Now by making $x_j \in \{-1,1\}$ we have a chance to wipe-out all terms which contain odd powers for some . This is done by multiplying the expression $t(x_1,x_2,x_3\ldots, x_{2n})$ by $e(x_1,x_2\ldots x_{2n})=x_1x_2x_3\dots x_{2n}$ by doing this every term in $e(x_1,\dots x_{2n})t(x_1,\dots ,x_{2n})$ will have at least one with odd power except the Langford term which will be $x_1^2x_2^2\ldots x_{2n}^2$ . Thus the summation on knocks out all the terms except the Langford terms as follows.

$\begin{displaymath} \begin{array}{l} f(x_1,x_2\ldots x_{2n}) = e(x_1,x_2,\ldots ... ...x_{2n}) = 2^{2n} (\text{no.of Langford pairs}) \par \end{array}\end{displaymath}$