A055093 -id:A055093 - cp's OEIS frontend

A055089 List of all finite permutations in reversed colexicographic ordering.

1, 2, 1, 1, 3, 2, 3, 1, 2, 2, 3, 1, 3, 2, 1, 1, 2, 4, 3, 2, 1, 4, 3, 1, 4, 2, 3, 4, 1, 2, 3, 2, 4, 1, 3, 4, 2, 1, 3, 1, 3, 4, 2, 3, 1, 4, 2, 1, 4, 3, 2, 4, 1, 3, 2, 3, 4, 1, 2, 4, 3, 1, 2, 2, 3, 4, 1, 3, 2, 4, 1, 2, 4, 3, 1, 4, 2, 3, 1, 3, 4, 2, 1, 4, 3, 2, 1, 1, 2, 3, 5, 4, 2, 1, 3, 5, 4, 1, 3, 2, 5, 4, 3, 1, 2

Offset: 0

Antti Karttunen, Apr 18 2000

			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 number of fixed terms and we get a list of rearrangements of the 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,...
Alternatively, if we take only the first n terms of each such infinite row, then the first n! rows give all permutations of the elements 1,2,...,n.

Antti Karttunen, Rows 0..719 of the irregular table, flattened.
Daniel Forgues, Tilman Piesk, et al., Orderings, OEIS Wiki.
Antti Karttunen, Ranking and unranking functions, OEIS Wiki.
Tilman Piesk, Permutations and partitions in the OEIS, Wikiversity.
Lorenzo Sauras-Altuzarra, Some arithmetical problems that are obtained by analyzing proofs and infinite graphs, arXiv:2002.03075 [math.NT], 2020.
Index entries for sequences related to factorial base representation
Index entries for sequences related to permutations

Inversion vectors: A007623, cycle counts: A055090, minimum number of transpositions: A055091, minimum number of adjacent transpositions: A034968, order of each permutation: A055092, number of non-fixed elements: A055093, positions of inverses: A056019, positions after Foata transform: A065181; positions of fixed-point-free involutions: A064640.
Cf. A057112, A060112, A060117, A060118, A060132, A060133.
Cf. A195663, array of the infinite rows.
This permutation list gives essentially the same information as A030298/A030299, but in a more compact way, by skipping those permutations of A030298 that start with a fixed element.
A220658(n) gives the rank r of the permutation of which the term at a(n) is an element.
A220659(n) gives the zero-based position (from the left) of that a(n) in that permutation of rank r.
A084558(r)+1 gives the size of the finite subsequence (of the r-th infinite, but finitary permutation) which has been included in this list.

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;

A055089L[n_] := Reverse@SortBy[DeleteCases[Permutations@Range@n, {, n}], Reverse]; Flatten@Array[A055089L, 4] (* JungHwan Min, Aug 28 2016 *)

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

Name changed by Tilman Piesk, Feb 01 2012

A060129 Number of moved (non-fixed) elements in the permutation with rank number n in lists A060117 (or in A060118), i.e., the sum of the lengths of all cycles larger than one in that permutation.

Original entry on oeis.org

0, 2, 2, 3, 2, 3, 2, 4, 3, 4, 3, 4, 2, 3, 3, 4, 4, 4, 2, 3, 4, 4, 3, 4, 2, 4, 4, 5, 4, 5, 3, 5, 4, 5, 4, 5, 3, 4, 4, 5, 5, 5, 3, 4, 5, 5, 4, 5, 2, 4, 3, 4, 3, 4, 3, 5, 4, 5, 4, 5, 4, 5, 4, 5, 5, 5, 4, 5, 5, 5, 4, 5, 2, 3, 3, 4, 4, 4, 4, 5, 4, 5, 5, 5, 3, 4, 4, 5, 5, 5, 4, 4, 5, 5, 5, 5, 2, 3, 4, 4, 3, 4, 4, 5, 5, 5, 4, 5, 4, 4, 5, 5, 5, 5, 3, 4, 5, 5, 4, 5, 2

Offset: 0

Antti Karttunen, Mar 05 2001

nonn

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

Cf. also A000142, A055093, A060117, A060118, A060120, A060128, A060130, A084558, A275851.

a(n) = A060128(n) + A060130(n).
From Antti Karttunen, Aug 11 2016: (Start)
a(n) = A275812(A275725(n)).
a(n) = 1 + A084558(n) - A275851(n).
Other identities. For all n >= 0:
a(n) = A055093(A060120(n)).
a(A000142(n)) = 2.
(End)

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

Original entry on oeis.org

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

Antti Karttunen, Apr 18 2000

nonn

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

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

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

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.

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

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

Entry revised by Antti Karttunen, Dec 30 2017

A290095 a(n) = A275725(A060126(n)); prime factorization encodings of cycle-polynomials computed for finite permutations listed in reversed colexicographic ordering.

Original entry on oeis.org

2, 4, 18, 8, 8, 12, 150, 100, 54, 16, 16, 24, 54, 16, 90, 40, 36, 16, 16, 24, 40, 60, 16, 36, 1470, 980, 882, 392, 392, 588, 750, 500, 162, 32, 32, 48, 162, 32, 270, 80, 108, 32, 32, 48, 80, 120, 32, 72, 750, 500, 162, 32, 32, 48, 1050, 700, 378, 112, 112, 168, 450, 200, 162, 32, 32, 72, 200, 300, 32, 48, 108, 32, 162, 32, 270, 80, 108, 32, 378, 112, 630, 280

Offset: 0

Antti Karttunen, Aug 17 2017

nonn

In this context "cycle-polynomials" are single-variable polynomials where the coefficients (encoded with the exponents of prime factorization of n) are equal to the lengths of cycles in the permutation listed with index n in table A055089 (A195663). See the examples.

			Consider the first eight permutations (indices 0-7) listed in A055089:
  1 [Only the first 1-cycle explicitly listed thus a(0) = 2^1 = 2]
  2,1 [One transposition (2-cycle) in beginning, thus a(1) = 2^2 = 4]
  1,3,2 [One fixed element in beginning, then transposition, thus a(2) = 2^1 * 3^2 = 18]
  3,1,2 [One 3-cycle, thus a(3) = 2^3 = 8]
  2,3,1 [One 3-cycle, thus a(4) = 2^3 = 8]
  3,2,1 [One transposition jumping over a fixed element, a(5) = 2^2 * 3^1 = 12]
  1,2,4,3 [Two 1-cycles, then a 2-cycle, thus a(6) = 2^1 * 3^1 * 5^2 = 150].
  2,1,4,3 [Two 2-cycles, not crossed, thus a(7) = 2^2 * 5^2 = 100].

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

Cf. A055090, A055091, A055092, A055093, A060126, A290096, A290097.

Cf. also A275725, A275734, A275735, A276076 and tables A055089, A195663.

a(n) = A275725(A060126(n)).
Other identities:
A046523(a(n)) = A290096(n).
A056170(a(n)) = A055090(n).
A046660(a(n)) = A055091(n).
A072411(a(n)) = A055092(n).
A275812(a(n)) = A055093(n).

A055090 Number of cycles (excluding fixed points) of the n-th finite permutation in reversed colexicographic ordering (A055089).

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2

Offset: 0

Antti Karttunen, Apr 18 2000

nonn

Among the first n! entries k appears A136394(n,k) times. - Tilman Piesk, Apr 06 2012

Tilman Piesk, Table of n, a(n) for n = 0..5039
Tilman Piesk, Table for A198380 (a[n] is the number of addends in parentheses on the right of this table)
Tilman Piesk, Permutations and partitions in the OEIS (Wikiversity)
Index entries for sequences related to factorial base representation

Cf. A195663, A195664, A055089 (ordered finite permutations).
Cf. A198380 (cycle type of the n-th finite permutation).
Cf. A136394, A055089, A055090, A055093, A055091, A060128, A290095.

with(group); seq(nops(convert(PermRevLexUnrank(j),'disjcyc')),j=0..)];
# Procedure PermRevLexUnrank given in A055089.

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

a(n) = A056170(A290095(n)) = A060128(A060126(n)). - Antti Karttunen, Dec 30 2017

Name changed by Tilman Piesk, Apr 06 2012

A369376 a(n) is the number of elements p(j) > j (right displacements) in the n-th permutation in lexicographic order.

Original entry on oeis.org

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

Offset: 0

Joerg Arndt, Jan 22 2024

nonn

			In the following dots are used for zeros in the permutations and their inverses.
   n:    permutation    inv. perm.   a(n)
   0:    [ . 1 2 3 ]    [ . 1 2 3 ]   0
   1:    [ . 1 3 2 ]    [ . 1 3 2 ]   1
   2:    [ . 2 1 3 ]    [ . 2 1 3 ]   1
   3:    [ . 2 3 1 ]    [ . 3 1 2 ]   2
   4:    [ . 3 1 2 ]    [ . 2 3 1 ]   1
   5:    [ . 3 2 1 ]    [ . 3 2 1 ]   1
   6:    [ 1 . 2 3 ]    [ 1 . 2 3 ]   1
   7:    [ 1 . 3 2 ]    [ 1 . 3 2 ]   2
   8:    [ 1 2 . 3 ]    [ 2 . 1 3 ]   2
   9:    [ 1 2 3 . ]    [ 3 . 1 2 ]   3
  10:    [ 1 3 . 2 ]    [ 2 . 3 1 ]   2
  11:    [ 1 3 2 . ]    [ 3 . 2 1 ]   2
  12:    [ 2 . 1 3 ]    [ 1 2 . 3 ]   1
  13:    [ 2 . 3 1 ]    [ 1 3 . 2 ]   2
  14:    [ 2 1 . 3 ]    [ 2 1 . 3 ]   1
  15:    [ 2 1 3 . ]    [ 3 1 . 2 ]   2
  16:    [ 2 3 . 1 ]    [ 2 3 . 1 ]   2
  17:    [ 2 3 1 . ]    [ 3 2 . 1 ]   2
  18:    [ 3 . 1 2 ]    [ 1 2 3 . ]   1
  19:    [ 3 . 2 1 ]    [ 1 3 2 . ]   1
  20:    [ 3 1 . 2 ]    [ 2 1 3 . ]   1
  21:    [ 3 1 2 . ]    [ 3 1 2 . ]   1
  22:    [ 3 2 . 1 ]    [ 2 3 1 . ]   2
  23:    [ 3 2 1 . ]    [ 3 2 1 . ]   2

Joerg Arndt, Table of n, a(n) for n = 0..40319

Cf. A369377, A055093, A034968.

a(n) + A369377(n) = A055093(n).

A369377 a(n) is the number of elements p(j) < j (left displacements) in the n-th permutation in lexicographic order.

Original entry on oeis.org

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

Offset: 0

Joerg Arndt, Jan 22 2024

nonn

			In the following dots are used for zeros in the permutations and their inverses.
   n:    permutation    inv. perm.   a(n)
   0:    [ . 1 2 3 ]    [ . 1 2 3 ]   0
   1:    [ . 1 3 2 ]    [ . 1 3 2 ]   1
   2:    [ . 2 1 3 ]    [ . 2 1 3 ]   1
   3:    [ . 2 3 1 ]    [ . 3 1 2 ]   1
   4:    [ . 3 1 2 ]    [ . 2 3 1 ]   2
   5:    [ . 3 2 1 ]    [ . 3 2 1 ]   1
   6:    [ 1 . 2 3 ]    [ 1 . 2 3 ]   1
   7:    [ 1 . 3 2 ]    [ 1 . 3 2 ]   2
   8:    [ 1 2 . 3 ]    [ 2 . 1 3 ]   1
   9:    [ 1 2 3 . ]    [ 3 . 1 2 ]   1
  10:    [ 1 3 . 2 ]    [ 2 . 3 1 ]   2
  11:    [ 1 3 2 . ]    [ 3 . 2 1 ]   1
  12:    [ 2 . 1 3 ]    [ 1 2 . 3 ]   2
  13:    [ 2 . 3 1 ]    [ 1 3 . 2 ]   2
  14:    [ 2 1 . 3 ]    [ 2 1 . 3 ]   1
  15:    [ 2 1 3 . ]    [ 3 1 . 2 ]   1
  16:    [ 2 3 . 1 ]    [ 2 3 . 1 ]   2
  17:    [ 2 3 1 . ]    [ 3 2 . 1 ]   2
  18:    [ 3 . 1 2 ]    [ 1 2 3 . ]   3
  19:    [ 3 . 2 1 ]    [ 1 3 2 . ]   2
  20:    [ 3 1 . 2 ]    [ 2 1 3 . ]   2
  21:    [ 3 1 2 . ]    [ 3 1 2 . ]   1
  22:    [ 3 2 . 1 ]    [ 2 3 1 . ]   2
  23:    [ 3 2 1 . ]    [ 3 2 1 . ]   2

Joerg Arndt, Table of n, a(n) for n = 0..40319

Cf. A369376, A055093, A034968.

a(n) + A369376(n) = A055093(n).

cp's OEIS Frontend

A055089 List of all finite permutations in reversed colexicographic ordering.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A060129 Number of moved (non-fixed) elements in the permutation with rank number n in lists A060117 (or in A060118), i.e., the sum of the lengths of all cycles larger than one in that permutation.

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

Extensions

A290095 a(n) = A275725(A060126(n)); prime factorization encodings of cycle-polynomials computed for finite permutations listed in reversed colexicographic ordering.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A055090 Number of cycles (excluding fixed points) of the n-th finite permutation in reversed colexicographic ordering (A055089).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A369376 a(n) is the number of elements p(j) > j (right displacements) in the n-th permutation in lexicographic order.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A369377 a(n) is the number of elements p(j) < j (left displacements) in the n-th permutation in lexicographic order.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula