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

## No comments:

Post a Comment