# Number of permutations which have the same Kendall-Tau distance

Input: The number of elements $m$ and an (positive) integer distance $d$.
Ouput: The number of permutations of $m$ elements which have Kendall-Tau distance $d$ from a fixed permutation.

I think there should be a closed formula. Does anybody know a good reference?

• The Kendall-Tau distance is also known as the bubble-sort distance. Does this SO question answer your question?
– Juho
Mar 13, 2012 at 11:43
• It does! Although not as easy as I hoped, it provides a nice polynomial-time algorithm which should be sufficient for my application. Thanks a lot. Mar 13, 2012 at 13:51
• Does this sequence in OEIS help? Mar 13, 2012 at 13:51
• @mrm comment-> answer ? Mar 13, 2012 at 17:37