Tuesday, September 01, 2009

Algebraic methods for Combinatorial counting.

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 $ 2n$ integers - every integer $ 1\leq i \leq n$ is repeated exactly twice. A Langford pair $ l$ is a permutation $ \pi$ of $ S$ , with a property that there are exactly $ i \in S$ elements between $ i$ and its copy, $ 1\leq i \leq n$ . (e.g. for $ n=3$ $ L = \{ 3,1,2,1,3,2 \}$ , we can see that $ 1$ and its copy has exactly $ 1$ element between them. Also observe the property of $ 2$ and $ 3$ ) 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 $ L_n$ 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 $ l$ , 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 $ k$ appears at position $ j$ in the permutation, then none of the integers except $ k$ can occur at position $ j+k+1$ - which is towards the right. Also note that the integer $ k$ 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 $ S$ , the integer $ 4$ can only occur at positions $ 1\leq j \leq 3$ . Similarly integer $ 1$ 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 $ P'$ 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 $ P'(k)+k+1$ , we should not see any duplicates. Now all possible function mappings of $ P'$ 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 $ P$ (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 $ x_j$ . 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 $ x_j$ 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}

Vamsi Kundeti 2009-09-02
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)