ca.analysis and odes - Applications of Measure, Integration and Banach Spaces to Combinatorics

Here's a nice application of measure theory, precisely, of the the theory of orthogonal polynomials, to a classic problem of counting derangements.

Problem: How many anagrams with no fixed letters of a given word are there?

For instance, for a word made of only two different letters, say $n$ letters $A$ and $m$ letters $B$, the answer is, of course, 1 or 0 according whether $n = m$ or not, for the only way to form an anagram without fixed letters is, exchanging all the $A$ with $B$, and this is possible if and only if $n=m$.

In the general case, for a word with $n_1$ letters $X_1$, $n_2$ letters $X_2$, ..., $n_r$ letters $X_r$, you will find (after the proper use of the inclusion-exclusion formula) that the answer has the form of a sum of products, that looks very much like the expansion of a product of sums, yet it is not. It is not, exactly because of the presence of terms $k!$, that would formally make a true expansion of a product of sums, if only they where replaced by corresponding terms $x^k$. This suggests to express them with the Eulerian integral $k!=int_0^infty x^ke^{-x}dx$, with the effect that the said expression becomes an integral (with the weight $e^{-x}$) of a true product of sums: precisely,

$$int_0^infty P_{n_1} (x) P_{n_2}(x)cdots P_{n_r}(x), e^{-x}, dx,$$

with a certain sequence of polynomials $P_n$, where $P_n$, has degree $n$. But the above answer for the case $r=2$ gives an orthogonality relation, whence the $P_n$, are the Laguerre polynomials, (up to a sign that is easily decided). Note that in the case with no repeated letters, all $n_i=1$, one finds again the more popular enumeration of permutations without fixed points.

Disclaimer: I partially copied this from wikipedia; it's me who wrote it there. The above is my personal amateur's solution, and possibly differs slightly from the vulgata. An on-line reference, with generalizations of the problem, is e.g.

Weighted derangements and Laguerre polynomials, D.Foata and D.Zeilberger, SIAM J. Discrete Math. 1 (1988) 425-433.