0,2

[seq(op(PermRevLexUnrank(j)), j=0..)]; (see Maple code given below).

In this table each row consists of A001563[n] permutations of (n+1) terms; i.e. we have (1/) 2,1/ 1,3,2; 3,1,2; 2,3,1; 3,2,1/ 1,2,4,3; 2,1,4,3;

Append to each an infinite amount of fixed terms and we get a list of rearrangements of natural numbers, but with only a finite number of terms permuted:

1/2,3,4,5,6,7,8,9,...

2,1/3,4,5,6,7,8,9,...

1,3,2/4,5,6,7,8,9,...

3,1,2/4,5,6,7,8,9,...

2,3,1/4,5,6,7,8,9,...

3,2,1/4,5,6,7,8,9,...

1,2,4,3/5,6,7,8,9,...

2,1,4,3/5,6,7,8,9,...

Or alternatively, if we take only n first terms of each such infinite row, then n! first rows give all permutations of the elements 1,2,...,n.

factorial_base := proc(nn) local n, a, d, j, f; n := nn; if(0 = n) then RETURN([0]); fi; a := []; f := 1; j := 2; while(n > 0) do d := floor(`mod`(n, (j*f))/f); a := [d, op(a)]; n := n - (d*f); f := j*f; j := j+1; od; RETURN(a); end;

fexlist2permlist := proc(a) local n, b, j; n := nops(a); if(0 = n) then RETURN([1]); fi; b := fexlist2permlist(cdr(a)); for j from 1 to n do if(b[j] >= ((n+1)-a[1])) then b[j] := b[j]+1; fi; od; RETURN([op(b), (n+1)-a[1]]); end;

fac_base := n -> fac_base_aux(n, 2); fac_base_aux := proc(n, i) if(0 = n) then RETURN([]); else RETURN([op(fac_base_aux(floor(n/i), i+1)), (n mod i)]); fi; end;

PermRevLexUnrank := n -> `if`((0 = n), [1], fexlist2permlist(fac_base(n)));

cdr := proc(l) if 0 = nops(l) then ([]) else (l[2..nops(l)]); fi; end; # "the tail of the list"

# Same algorithm in different guise, showing how permutations are composed of adjacent transpositions (compare to algorithm PermUnrank3R at A060117):

PermRevLexUnrankAMSDaux := proc(n, r, pp) local s, p, k; p := pp; if(0 = r) then RETURN(p); else s := floor(r/((n-1)!)); for k from n-s to n-1 do p := permul(p, [[k, k+1]]); od; RETURN(PermRevLexUnrankAMSDaux(n-1, r-(s*((n-1)!)), p)); fi; end;

PermRevLexUnrankAMSD := proc(r) local n; n := nops(factorial_base(r)); convert(PermRevLexUnrankAMSDaux(n+1, r, []), 'permlist', 1+(((r+2) mod (r+1))*n)); end;

Inversion vectors: A007623, cycle counts: A055090, minim. number of transpositions: A055091, minim. number of adjacent transpositions: A034968, order of each perm.: A055092, number of non-fixed elements: A055093, positions of inverses: A056019, positions after Foata transform: A065181.

Cf. A057112, A060112, A060117, A060118, A060132, A060133.

Positions of fixed-point-free involutions: A064640.

Sequence in context: A006843 A049456 A117506 this_sequence A060117 A112592 A070036

Adjacent sequences: A055086 A055087 A055088 this_sequence A055090 A055091 A055092

nonn,tabf

Antti Karttunen Apr 18 2000