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?

  • $\begingroup$ The Kendall-Tau distance is also known as the bubble-sort distance. Does this SO question answer your question? $\endgroup$
    – Juho
    Commented Mar 13, 2012 at 11:43
  • $\begingroup$ 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. $\endgroup$
    – RBredereck
    Commented Mar 13, 2012 at 13:51
  • 4
    $\begingroup$ Does this sequence in OEIS help? $\endgroup$ Commented Mar 13, 2012 at 13:51
  • 3
    $\begingroup$ @mrm comment-> answer ? $\endgroup$ Commented Mar 13, 2012 at 17:37

1 Answer 1


This StackOverflow question answers your question. You might also be interested in this OEIS sequence.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.