A Problem From The 2005 Putnam Competition
A link to the Putnam competition website appears in the section External links. The problem asks for a proof that
where the sum is over all permutations of, is the sign of, i.e. if is even and if is odd, and is the number of fixed points of .
Now the sign of is given by
where the product is over all cycles c of, as explained e.g. on the page on even and odd permutations.
Hence we consider the combinatorial class
where marks one minus the length of a contributing cycle, and marks fixed points. Translating to generating functions, we obtain
or
Now we have
and hence the desired quantity is given by
Doing the computation, we obtain
or
Extracting coefficients, we find that the coefficient of is zero. The constant is one, which does not agree with the formula (should be zero). For positive, however, we obtain
or
which is the desired result.
As an interesting aside, we observe that may be used to evaluate the following determinant of an matrix:
where . Recall the formula for the determinant:
Now the value of the product on the right for a permutation is, where f is the number of fixed points of . Hence
which yields
and finally
Read more about this topic: Random Permutation Statistics
Famous quotes containing the words problem, putnam and/or competition:
“The family environment in which your children are growing up is different from that in which you grew up. The decisions our parents made and the strategies they used were developed in a different context from what we face today, even if the content of the problem is the same. It is a mistake to think that our own experience as children and adolescents will give us all we need to help our children. The rules of the game have changed.”
—Lawrence Kutner (20th century)
“Men, you are all marksmendont one of you fire until you see the whites of their eyes.”
—Israel Putnam (17181790)
“Like many businessmen of genius he learned that free competition was wasteful, monopoly efficient. And so he simply set about achieving that efficient monopoly.”
—Mario Puzo (b. 1920)