Yesterday I wrote a couple of posts about a combinatorics question that lead to OEIS sequence A000255. That page has this intriguing line:
This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010)
I love how pulling on a thread can lead you to unexpected places. What in the world does my little permutation problem have to do with particle physics‽
I found Malin Sjödahl’s website, and apparently the citation above refers to this paper from 2009. The author’s site doesn’t list any papers from 2010. Maybe the paper was published electronically in 2009 and in print in 2010.
Counting tensors
The paper is mostly opaque to me since I don’t know particle physics, but at one point Sjödahl says
The problem of finding all such topologies is equivalent to the number of ways of mapping N elements to each other without mapping a single one to itself …
and says that the solution is
Sjödahl is not counting physical permutations but the number possible tensors associated with gluons and quark interaction diagrams.
The right-hand side above is essentially the same as the asymptotic estimate for the function Q(n) in the previous post.
I didn’t find the recurrence that the OEIS comment alluded to. Perhaps I’m not looking at the same paper. Perhaps I’m not looking hard enough because I’m skimming a paper whose contents I don’t understand.
The Montmort letter problem
In more mathematical terminology, Sjödahl is counting the number of permutations of N objects with no fixed point, known as the number derangements of a set N objects.
If you divide by the number of possible permutations N! you have the probability that a random permutation moves every object.
This was historically known as the Montmort letter problem, named after Pierre-Remond Montmort who asked the following question. If N letters are randomly assigned to N envelopes, what is the probability that no letter ends up in the correct envelope?
The probability converges to 1/e as N approaches infinity. It approaches 1/e quickly, and so this is a good approximation even for moderate N. More on the rate of convergence in the next post.