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 .
- 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
can occur at position
- which is towards the right.
Also note that the integer
can only occur at positions
, for example, in any Langford permutation of
can only occur at positions
. Similarly integer
occur at positions
. Now this explains the intuition behind
in the definition of the function
be a function - we call
it a position map. Which maps every integer
to a index/position in the permutation
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.
- 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 doing this every term in
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