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.
It’s not extremely clear, so it would take some detective work. OEIS sequence A000255, Wolfdieter Lang writes:
“a(n), n >= 1, enumerates also the ways to distribute n beads, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and one open cord allowed to have any number of beads. Each beadless necklace as well as the beadless cord contributes a factor 1 in the counting, e.g., a(0):=1*1=1. There are k! possibilities for the cord with k>=0 beads, which means that the two ends of the cord should be considered as fixed, in short: a fixed cord.
Alternatively, the e.g.f. for this problem is seen to be (exp(-x)/(1-x))*(1/(1-x)), namely the product of the e.g.f.s for the subfactorials (from the unordered necklace problem, without necklaces with exactly one bead) and the factorials (from the fixed cord problem). Therefore the recurrence with inputs holds also. a(0):=1. 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). ”
This needs to be carefully correlated with Sjodahl’s remarks in section 2.3 of his paper “Color structure for soft gluon resummation — a
general recipe”, beginning
“The problem of constructing the N-gluon basis in the general case thus boils down to…”
and continuing on with the description of a 3-part recursive algorithm. In the end he concludes “the possible color tensors coincide with the color tensors obtained by replacing each gluon with one quark and one anti-quark line, with the important exception that contractions between a qq pair corresponding to
the same gluon are disallowed. 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” – so then he counts derangements.
I believe a careful analysis of what Sjodahl wrote should give the formula Wolfdieter Lang writes. It’s not at all obvious! Luckily I don’t think one needs to know very deep physics to sift through this; it mainly requires familiarity with what Feynman diagrams look like, and these are purely combinatorial entities. I feel I could do it in a couple days of hard work.
In practice the fastest way might be to email Wolfdieter Lang, who is at Karlsruhe. He looks more like a mathematician attracted to counting problems than a physicist, with arXiv papers like “Four Sequences of Length 28 and the Gregorian Calendar” and “The Tribonacci and ABC Representations of Numbers are Equivalent”.
I add that in the article https://arxiv.org/abs/2309.08841 on page 4 the e.g.f. is derived from the recurrence relation
I want to add the answer that Prof. Lang kindly sent to me about the topic:
“A quick look into my notes shows: Malin Sjödahl uses States[Nq_, Ng_] for what I named T_n^(a) (here just T(a,n)), with n = N_g (gluon numbers) amd a = N_q = N_{qbar} )quark, antiquark numbers).
Then her recurrence was:
T(a, n) = (a-n-1)*T(a, n-1) + (n-1)*T(a,n-2), with input T(a,-1) =0, T(a. 0) = a! (T(a, 1) = a*a!).
The I took t^(a)(n) = t(a,n) as t(a,n) = T(a.n)/n! (because ofsymmetry in the Nq = a numbers), hence I solved later
T(a, n) = (a-n-1)^t(a, n-1( + (n-1)*t(a,n-2), input t(-1, a) =0, t(0,1) =1. (t(a, 1) = a).
I computed the expomential generating function (e.g.f)
t(a;x) = Sum_{n=0 or 1)} t(a.n)*x^n/n!
= (exp(-x)/(1-x))* (1/ (1 – x)^a = exp(-x)/(1 – x)^{a+1}
(related to necklaces with numbered beads and open chains with numbered beads).
You have to figure out the corespondimg quark-gluon diagrams, using that no tadpoles (1 gloun and one Quark line) due to the trace of the SU(3) generator being 0.
Then we gave together special cases in OEIS, see
https://oeis.org/A145573
and
https://oeis.org/A145574“