A055091 Minimum number of transpositions needed to represent each permutation given in reversed colexicographic ordering A055089.

0, 1, 1, 2, 2, 1, 1, 2, 2, 3, 3, 2, 2, 3, 1, 2, 2, 3, 3, 2, 2, 1, 3, 2, 1, 2, 2, 3, 3, 2, 2, 3, 3, 4, 4, 3, 3, 4, 2, 3, 3, 4, 4, 3, 3, 2, 4, 3, 2, 3, 3, 4, 4, 3, 1, 2, 2, 3, 3, 2, 2, 3, 3, 4, 4, 3, 3, 2, 4, 3, 3, 4, 3, 4, 2, 3, 3, 4, 2, 3, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 3, 3, 4, 2, 3, 4, 3, 3, 2, 4, 3, 3, 2, 2

Offset: 0

Author

Antti Karttunen, Apr 18 2000

Keywords

• nonn

Links

• Antti Karttunen, Table of n, a(n) for n = 0..40320
• Index entries for sequences related to factorial base representation

Crossrefs

Cf. A046660, A055089, A055090, A055093, A060130, A290095.

Cf. also A034968 (minimum number of adjacent transpositions).

Programs

Maple

with(group); [seq(count_transpositions(convert(PermRevLexUnrank(j),'disjcyc')),j=0..)];
count_transpositions := proc(l) local c,t; t := 0; for c in l do t := t + (nops(c)-1); od; RETURN(t); end;
# Procedure PermRevLexUnrank given in A055089.

Formula

a(n) = A055093(n) - A055090(n).

a(n) = A046660(A290095(n)) = A060130(A060126(n)). - Antti Karttunen, Dec 30 2017

Extensions

Entry revised by Antti Karttunen, Dec 30 2017