5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ The Kendall-Tau distance is also known as the bubble-sort distance. Does this SO question answer your question? $\endgroup$
    – Juho
    Mar 13 '12 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
    Mar 13 '12 at 13:51
  • 4
    $\begingroup$ Does this sequence in OEIS help? $\endgroup$
    – Anthony Labarre
    Mar 13 '12 at 13:51
  • 3
    $\begingroup$ @mrm comment-> answer ? $\endgroup$
    – Suresh Venkat
    Mar 13 '12 at 17:37
6
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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