## 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 of integers - every integer is repeated exactly twice. A Langford pair is a permutation of , with a property that there are exactly elements between and its copy, . (e.g. for , 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 .
• Let
• Let
• Show that

Looking at the problem first, I was a little unclear what is the intuition behind defining such a function (i.e. ). After careful thought and analysis I understood that the function 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 .

• Consider a Langford permutation , now consider the positions of each integer 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 . Let , for example, in any Langford permutation of , the integer can only occur at positions . Similarly integer can occur at positions . Now this explains the intuition behind in the definition of the function .

• Let be a function - we call it a position map. Which maps every integer to a index/position in the permutation . Let and . We now see that a position map can generate a Langford permutation only if . In other words the position mapping function should map the integers 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.

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 and . Now we are looking for all the possible terms which have , 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 . How do we do that ?, this is where the trick of odd , even functions come into play. Now by making we have a chance to wipe-out all terms which contain odd powers for some . This is done by multiplying the expression by by doing this every term in will have at least one with odd power except the Langford term which will be . Thus the summation on knocks out all the terms except the Langford terms as follows.

Vamsi Kundeti 2009-09-02