<p>This <a href="https://stackoverflow.com/questions/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble-sort-swaps">StackOverflow question</a> answers your question. You might also be interested in <a href="https://oeis.org/search?q=+kendall+tau&amp;sort=&amp;language=english&amp;go=Search" rel="nofollow noreferrer">this OEIS sequence</a>.</p>

CC BY-SA 3.0
2012-03-13T17:56:34.040Z
2012-03-13T17:56:34.040Z
2017-05-23T12:40:09.333Z
Juho
<p><strong>Input:</strong> The number of elements $m$ and an (positive) integer distance $d$.<br>
<strong>Ouput:</strong> The number of permutations of $m$ elements which have Kendall-Tau distance $d$ from a fixed permutation.</p>

<p>I think there should be a closed formula. Does anybody know a good reference?</p>

CC BY-SA 3.0
2012-03-13T11:43:50.937Z
The Kendall-Tau distance is also known as the bubble-sort distance. Does [this SO question](http://stackoverflow.com/questions/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble-sort-swaps) answer your question?
Juho
CC BY-SA 3.0
2012-03-13T13:51:02.930Z
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.
RBredereck
CC BY-SA 3.0
2012-03-13T13:51:57.407Z
Does [this sequence in OEIS](https://oeis.org/search?q=+kendall+tau&sort=&language=english&go=Search) help?
Anthony Labarre
CC BY-SA 3.0
2012-03-13T17:37:51.023Z
@mrm comment-> answer ?
Suresh Venkat
<ds.algorithms><co.combinatorics><permutations>
Number of permutations which have the same Kendall-Tau distance
RBredereck
# Number of permutations which have the same Kendall-Tau distance

(Asked by: username_0 on 2012-03-13)

**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?

**Tags:** ds.algorithms, co.combinatorics, permutations
> **Comments:**
> **username_1**: The Kendall-Tau distance is also known as the bubble-sort distance. Does [this SO question](http://stackoverflow.com/questions/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble-sort-swaps) answer your question?  
> **username_0**: 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.  
> **username_2**: Does [this sequence in OEIS](https://oeis.org/search?q=+kendall+tau&sort=&language=english&go=Search) help?  
> **username_3**: @mrm comment-> answer ?  

---

## 1 answers

### Answer by username_1 on 2012-03-13. Score: 6 | Accepted answer

This [StackOverflow question](https://stackoverflow.com/questions/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble-sort-swaps) answers your question. You might also be interested in [this OEIS sequence](https://oeis.org/search?q=+kendall+tau&sort=&language=english&go=Search).


---

