A055089 -id:A055089 - cp's OEIS frontend

A060126 Positions of permutations of A055089 in the permutation sequence A060117.

0, 1, 2, 3, 5, 4, 6, 7, 8, 9, 11, 10, 14, 15, 12, 13, 16, 17, 23, 22, 19, 18, 21, 20, 24, 25, 26, 27, 29, 28, 30, 31, 32, 33, 35, 34, 38, 39, 36, 37, 40, 41, 47, 46, 43, 42, 45, 44, 54, 55, 56, 57, 59, 58, 48, 49, 50, 51, 53, 52, 60, 61, 62, 63, 65, 64, 67, 66, 71, 70, 68, 69

Offset: 0

Antti Karttunen, Mar 02 2001

Together with the inverse A060119 this can be used to conjugate between "multiplication tables" of A261096 & A261216 (and for example, their main diagonals A261099 & A261219, or between involutions A056019 & A060125, see the Formula section) that have been computed for these two common alternative orderings of permutations. - Antti Karttunen, Sep 28 2016

Inverse: A060119.
Cf. A060132 (fixed points).
Cf. A055089, A060117.
Cf. also A056019, A060125, A060127, A261096, A261099, A261216, A261219.

# Procedure PermRank3R is given in A060125 and PermRevLexUnrank in A055089:
A060126(n) = PermRank3R(PermRevLexUnrank(n));

Other identities. For all n >= 0:

a(A056019(A060119(n))) = A060125(n).

Edited by Antti Karttunen, Sep 28 2016

A060119 Positions of permutations of A060117 in reversed colexicographic ordering A055089.

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 6, 7, 8, 9, 11, 10, 14, 15, 12, 13, 16, 17, 21, 20, 23, 22, 19, 18, 24, 25, 26, 27, 29, 28, 30, 31, 32, 33, 35, 34, 38, 39, 36, 37, 40, 41, 45, 44, 47, 46, 43, 42, 54, 55, 56, 57, 59, 58, 48, 49, 50, 51, 53, 52, 60, 61, 62, 63, 65, 64, 67, 66, 70, 71, 69, 68

Offset: 0

Antti Karttunen, Mar 02 2001

Together with the inverse A060126 this can be used to conjugate between "multiplication tables" of A261096 & A261216 (and for example, their main diagonals A261099 & A261219, or between involutions A056019 & A060125, see the Formula section) that have been computed for these two common alternative orderings of permutations. - Antti Karttunen, Sep 28 2016

Inverse: A060126.
Cf. A060132 (fixed points).
Cf. A055089, A060117.
Cf. also A056019, A060120, A060125, A261096, A261099, A261216, A261219.

# The procedure PermUnrank3R is given in A060117, and PermRevLexRank in A056019:
A060119(n) = PermRevLexRank(PermUnrank3R(n));

As a composition of other permutations:
a(n) = A056019(A060120(n)).
Other identities, for all n >= 0:
a(A060125(A060126(n))) = A056019(n).

Edited by Antti Karttunen, Sep 27 2016

A056019 Self-inverse infinite permutation which shows the position of each finite permutation's inverse permutation in A055089.

Original entry on oeis.org

0, 1, 2, 4, 3, 5, 6, 7, 12, 18, 13, 19, 8, 10, 14, 20, 16, 22, 9, 11, 15, 21, 17, 23, 24, 25, 26, 28, 27, 29, 48, 49, 72, 96, 73, 97, 50, 52, 74, 98, 76, 100, 51, 53, 75, 99, 77, 101, 30, 31, 36, 42, 37, 43, 54, 55, 78, 102, 79, 103, 60, 66, 84, 108, 90, 114, 61, 67, 85

Offset: 0

Antti Karttunen, Jun 08 2000

PermRevLexRank and PermRevLexUnrank have been modified from the algorithms PermLexRank and PermLexUnrank presented in the book "Combinatorial Algorithms, Generation, Enumeration and Search", by Donald L. Kreher and Douglas R. Stinson.

			E.g. the permutation [2,3,1] is the 4th permutation (counting from 0th, the identity permutation) of A055089, its inverse permutation is [3,1,2] which is 3rd, thus a(4)=3 and a(3)=4.

PermRevLexRank := proc(pp) local p,n,i,j,r; p := pp; n := nops(p); r := 0; for j from n by -1 to 1 do r := r + (((j-p[j])*((j-1)!))); for i from 1 to (j-1) do if(p[i] > p[j]) then p[i] := p[i]-1; fi; od; od; RETURN(r); end;
[seq(PermRevLexRank(convert(invperm(convert(PermRevLexUnrank(j), 'disjcyc')), 'permlist', nops(PermRevLexUnrank(j)))), j=0..200)];

A056019 = Position[Ordering /@ #, #[[#2]]][[1, 1]] - 1 &[Reverse@SortBy[Permutations@Range@Ceiling@InverseFunction[Factorial][# + 1], Reverse], # + 1] &; Array[A056019, 69, 0] (* JungHwan Min, Oct 10 2016 *)
A056019L = Ordering[Ordering /@ Permutations@Range@Ceiling@InverseFunction[Factorial][# + 1]] - 1 &; A056019L[24] (* JungHwan Min, Oct 10 2016 *)

A060120 Positions of permutations of A060118 in the canonical permutation list A055089.

Original entry on oeis.org

0, 1, 2, 4, 5, 3, 6, 7, 12, 18, 19, 13, 14, 20, 8, 10, 16, 22, 21, 15, 23, 17, 11, 9, 24, 25, 26, 28, 29, 27, 48, 49, 72, 96, 97, 73, 74, 98, 50, 52, 76, 100, 99, 75, 101, 77, 53, 51, 54, 55, 78, 102, 103, 79, 30, 31, 36, 42, 43, 37, 60, 66, 84, 108, 114, 90, 67, 61, 91

Offset: 0

Antti Karttunen, Mar 02 2001

nonn

Index entries for sequences that are permutations of the natural numbers

PermRevLexRank given in A056019. A060120[n] = A056019[A060119[n]] for all n.

Inverse permutation: A060127.

a(n) = PermRevLexRank(PermUnrank3L(n))

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

A055093 Number of moved (non-fixed) elements in each permutation given in reversed colexicographic ordering A055089, i.e., the sum of their cycle lengths (excluding the 1-cycles, i.e., fixed elements).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Apr 04 2000

nonn

Also number of displacements for permutations in lexicographic order. - Joerg Arndt, Jan 22 2024

Antti Karttunen, Table of n, a(n) for n = 0..40320
Tilman Piesk, Permutations and partitions in the OEIS (Wikiversity)
Index entries for sequences related to factorial base representation

Cf. A055089, A055090, A055091, A055092, A060129, A275812, A290095.

A055093(n) = count_nonfixed(convert(PermRevLexUnrank(j), 'disjcyc')).
count_nonfixed := l -> convert(map(nops,l), `+`);
# Procedure PermRevLexUnrank given in A055089.

a(n) = A055090(n) + A055091(n).

a(n) = A275812(A290095(n)) = A060129(A060126(n)). - Antti Karttunen, Dec 30 2017

Entry revised by Antti Karttunen, Dec 30 2017

A060127 Positions of permutations of A055089 in the permutation sequence A060118. Inverse permutation to A060120.

Original entry on oeis.org

0, 1, 2, 5, 3, 4, 6, 7, 14, 23, 15, 22, 8, 11, 12, 19, 16, 21, 9, 10, 13, 18, 17, 20, 24, 25, 26, 29, 27, 28, 54, 55, 86, 119, 87, 118, 56, 59, 84, 115, 88, 117, 57, 58, 85, 114, 89, 116, 30, 31, 38, 47, 39, 46, 48, 49, 74, 101, 75, 100, 60, 67, 80, 107, 93, 112, 61, 66

Offset: 0

Antti Karttunen, Mar 02 2001

nonn

Index entries for sequences that are permutations of the natural numbers

Cf. A060125, A060126, A060133.

a(n) = PermRank3L(PermRevLexUnrank(n))

A064640 Positions of non-crossing fixed-point-free involutions (encoded by A014486) in A055089, sorted to ascending order.

Original entry on oeis.org

0, 1, 7, 23, 127, 143, 415, 659, 719, 5167, 5183, 5455, 5699, 5759, 16687, 16703, 26815, 28495, 36899, 36959, 38579, 40031, 40319, 368047, 368063, 368335, 368579, 368639, 379567, 379583, 389695, 391375, 399779, 399839, 401459, 402911, 403199

Offset: 0

Antti Karttunen, Oct 02 2001

nonn

These permutations belong to the interpretation (kk) of the exercise 19 in the sixth chapter "Exercises on Catalan and Related Numbers" of Enumerative Combinatorics, Vol. 2, 1999 by R. P. Stanley, Wadsworth, Vol. 1, 1986: Fixed-point-free involutions w of [2n] such that if i < j < k < l and w(i) = k, then w(j) <> l.

From this, it follows that when they are subjected to the same automorphism as used in A061417 and A064636, one gets A002995.

			The first eight such permutations (after the identity) are in positions 1, 7, 23, 127, 143, 415, 659, 719 of A055089: 21, 2143, 4321, 214365, 432165, 216543, 632541, 654321 which written as disjoint cycles are (1 2), (1 2)(3 4), (1 4)(2 3), (1 2)(3 4)(5 6), (1 4)(2 3)(5 6), (1 2)(3 6)(4 5), (1 6)(2 3)(4 5), (1 6)(2 5)(3 4).

R. P. Stanley, Exercises on Catalan and Related Numbers

For the needed Maple procedures see A064638. Cf. also A064639, A060112.

Maple
```
sort(A064638); or sort(A064639);
```

A065181 Permutation of nonnegative integers produced when the finite permutations listed by A055089 are subjected to inverse of Foata's transformation. Inverse of A065182.

Original entry on oeis.org

0, 1, 2, 5, 3, 4, 6, 7, 14, 23, 17, 20, 8, 11, 12, 22, 13, 21, 9, 10, 16, 18, 15, 19, 24, 25, 26, 29, 27, 28, 54, 55, 86, 119, 95, 110, 62, 71, 78, 116, 79, 113, 65, 68, 92, 102, 89, 103, 30, 31, 38, 47, 41, 44, 48, 49, 84, 118, 94, 108, 50, 53, 80, 117, 83, 109, 51, 52

Offset: 0

Antti Karttunen, Oct 19 2001

nonn

Here we use the inverse of the left-right maxima variant of Foata's transformation, which works by rotating each cycle largest element first and then sorts the cycles to ascending order, according to that first (and largest) element of each.

I.M. Gessel and R. P. Stanley, Algebraic Enumeration, chapter 21 in Handbook of Combinatorics, Vol. 2, edited by R.L.Graham et al., The MIT Press, Mass, 1995, page 1045.

Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Index entries for sequences that are permutations of the natural numbers

A065161-A065163 give cycle counts and max lengths. Cf. also A065183, A065184 and A055089 and A056019 for the requisite Maple procedures.

[seq(PermRevLexRank(FoataInv(PermRevLexUnrank(j))),j=0..119)];
with(group); FoataInv := p -> map(op, sort([op(map(RotCycleLargestFirst,convert(p,`disjcyc`))),op(FixedCycles(p))], sortbyfirst));
sortbyfirst := (a,b) -> `if`((a[1] < b[1]),true,false);
FindLargest := proc(a) local i,m; m := 0; for i from 1 to nops(a) do if(0 = m) then m := i; else if(a[i] > a[m]) then m := i; fi; fi; od; RETURN(m); end;
RotCycleLargestFirst := proc(c) local x; x := FindLargest(c); if(x <= 1) then RETURN(c); else RETURN([op(c[x..nops(c)]),op(c[1..(x-1)])]); fi; end;
FixedCycles := proc(p) local a,i; a := []; for i from 1 to nops(p) do if(p[i] = i) then a := [op(a),[i]]; fi; od; RETURN(a); end;

A261096 A(i,j) = rank (in A055089) of the composition of the i-th and the j-th permutation in table A055089, which lists all finite permutations in reversed colexicographic ordering.

Original entry on oeis.org

0, 1, 1, 2, 0, 2, 3, 4, 3, 3, 4, 5, 0, 2, 4, 5, 2, 1, 5, 5, 5, 6, 3, 5, 4, 1, 4, 6, 7, 7, 4, 0, 0, 3, 7, 7, 8, 6, 12, 1, 3, 2, 8, 6, 8, 9, 10, 13, 13, 2, 1, 9, 10, 9, 9, 10, 11, 14, 12, 18, 0, 10, 11, 6, 8, 10, 11, 8, 15, 16, 19, 19, 11, 8, 7, 11, 11, 11, 12, 9, 16, 17, 20, 18, 0, 9, 11, 10, 7, 10, 12, 13, 18, 17, 14, 21, 22, 1, 1, 10, 6, 6, 9, 13, 13, 14, 19, 6, 15, 22, 23, 2, 0, 14, 7, 9, 8, 14, 12, 14

Offset: 0

Antti Karttunen, Aug 26 2015

The square array A(row>=0, col>=0) is read by downwards antidiagonals as: A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), A(0,3), A(1,2), A(2,1), A(3,0), ...
A(i,j) gives the rank (in ordering used by table A055089) of the permutation which is obtained by composing permutations p and q listed as the i-th and the j-th permutation in irregular table A055089 (note that the identity permutation is the 0th). Here the convention is that "permutations act of the left", thus, if p1 and p2 are permutations, then the product of p1 and p2 (p1 * p2) is defined such that (p1 * p2)(i) = p1(p2(i)) for i=1...
Each row and column is a permutation of A001477, because this is the Cayley table ("multiplication table") of an infinite enumerable group, namely, that subgroup of the infinite symmetric group (S_inf) which consists of permutations moving only finite number of elements.

			The top left corner of the array:
   0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...
   1,  0,  4,  5,  2,  3,  7,  6, 10, 11,  8,  9, 18, ...
   2,  3,  0,  1,  5,  4, 12, 13, 14, 15, 16, 17,  6, ...
   3,  2,  5,  4,  0,  1, 13, 12, 16, 17, 14, 15, 19, ...
   4,  5,  1,  0,  3,  2, 18, 19, 20, 21, 22, 23,  7, ...
   5,  4,  3,  2,  1,  0, 19, 18, 22, 23, 20, 21, 13, ...
   6,  7,  8,  9, 10, 11,  0,  1,  2,  3,  4,  5, 14, ...
   7,  6, 10, 11,  8,  9,  1,  0,  4,  5,  2,  3, 20, ...
   8,  9,  6,  7, 11, 10, 14, 15, 12, 13, 17, 16,  0, ...
   9,  8, 11, 10,  6,  7, 15, 14, 17, 16, 12, 13, 21, ...
  10, 11,  7,  6,  9,  8, 20, 21, 18, 19, 23, 22,  1, ...
  11, 10,  9,  8,  7,  6, 21, 20, 23, 22, 18, 19, 15, ...
  12, 13, 14, 15, 16, 17,  2,  3,  0,  1,  5,  4,  8, ...
  ...
For A(1,2) (row=1, column=2, both starting from zero), we take as permutation p the permutation which has rank=1 in the ordering used by A055089, which is a simple transposition (1 2), which we can extend with fixed terms as far as we wish (e.g., like {2,1,3,4,5,...}), and as permutation q we take the permutation which has rank=2 (in the same list), which is {1,3,2}. We compose these from the left, so that the latter one, q, acts first, thus c(i) = p(q(i)), and the result is permutation {2,3,1}, which is listed as the 4th one in A055089, thus A(1,2) = 4.
For A(2,1) we compose those two permutations in opposite order, as d(i) = q(p(i)), which gives permutation {3,1,2} which is listed as the 3rd one in A055089, thus A(2,1) = 3.

Antti Karttunen, Table of n, a(n) for n = 0..10439; the first 144 antidiagonals of array
Wikipedia, Cayley table

Transpose: A261097.
Row 0 & Column 0: A001477 (identity permutation).
Row 1: A261098.
Column 1: A004442.
Main diagonal: A261099.
Cf. tables A055089, A195663.
Cf. also A261216, A261217 (similar arrays, but using different orderings of permutations).
Permutations used in conjugation-formulas: A056019, A060119, A060120, A060126, A060127.

By conjugating with related permutations and arrays:
A(i,j) = A056019(A261097(A056019(i),A056019(j))).
A(i,j) = A060119(A261216(A060126(i),A060126(j))).
A(i,j) = A060120(A261217(A060127(i),A060127(j))).

cp's OEIS Frontend

A060126 Positions of permutations of A055089 in the permutation sequence A060117.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A060119 Positions of permutations of A060117 in reversed colexicographic ordering A055089.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A056019 Self-inverse infinite permutation which shows the position of each finite permutation's inverse permutation in A055089.

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

A060120 Positions of permutations of A060118 in the canonical permutation list A055089.

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

A055093 Number of moved (non-fixed) elements in each permutation given in reversed colexicographic ordering A055089, i.e., the sum of their cycle lengths (excluding the 1-cycles, i.e., fixed elements).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A060127 Positions of permutations of A055089 in the permutation sequence A060118. Inverse permutation to A060120.

Views

Author

Keywords

Links

Crossrefs

Formula

A064640 Positions of non-crossing fixed-point-free involutions (encoded by A014486) in A055089, sorted to ascending order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A065181 Permutation of nonnegative integers produced when the finite permutations listed by A055089 are subjected to inverse of Foata's transformation. Inverse of A065182.

Views