A060126 -id:A060126 - cp's OEIS frontend

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

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).

A060132 Positions of the permutations which have the same rank in A055089 and A060117, i.e., the fixed points of permutations A060119 and A060126.

Original entry on oeis.org

0, 1, 2, 3, 6, 7, 8, 9, 16, 17, 24, 25, 26, 27, 30, 31, 32, 33, 40, 41, 60, 61, 62, 63, 120, 121, 122, 123, 126, 127, 128, 129, 136, 137, 144, 145, 146, 147, 150, 151, 152, 153, 160, 161, 180, 181, 182, 183, 288, 289, 290, 291, 294, 295, 296, 297, 304, 305, 316

Offset: 0

Antti Karttunen, Mar 02 2001

nonn

Cf. A060133. Includes A059590 as a subset and A064637 gives the terms that are not found therein.

sub1 := n -> (n - 1); map(sub1,positions(0,[seq(PermRank3R(PermRevLexUnrank(n))-n,n=0..1024)])); or map(sub1,positions(0,[seq(PermRevLexRank(PermUnrank3R(n))-n,n=0..1024)]));

A060125 Self-inverse infinite permutation which shows the position of the inverse of each finite permutation in A060117 (or A060118) in the same sequence; or equally, the cross-indexing between A060117 and A060118.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Mar 02 2001

PermRank3Aux is a slight modification of rank2 algorithm presented in Myrvold-Ruskey article.

Antti Karttunen, Table of n, a(n) for n = 0..5040
W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time, Inform. Process. Lett. 79 (2001), no. 6, 281-284.
Index entries for sequences related to factorial base representation
Index entries for sequences that are permutations of the natural numbers

Cf. A060117, A060118, A060126, A060127, A275957, A275958.
Cf. A261220 (fixed points).
Cf. A056019 (compare the scatter plots).

with(group); permul := (a,b) -> mulperms(b,a); swap := (p,i,j) -> convert(permul(convert(p,'disjcyc'),[[i,j]]),'permlist',nops(p));
PermRank3Aux := proc(n, p, q) if(1 = n) then RETURN(0); else RETURN((n-p[n])*((n-1)!) + PermRank3Aux(n-1,swap(p,n,q[n]),swap(q,n,p[n]))); fi; end;
PermRank3R := p -> PermRank3Aux(nops(p),p,convert(invperm(convert(p,'disjcyc')),'permlist',nops(p)));
PermRank3L := p -> PermRank3Aux(nops(p),convert(invperm(convert(p,'disjcyc')),'permlist',nops(p)),p);
# a(n) = PermRank3L(PermUnrank3R(n)) or PermRank3R(PermUnrank3L(n)) or PermRank3L(convert(invperm(convert(PermUnrank3L(j), 'disjcyc')), 'permlist', nops(PermUnrank3L(j))))

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

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))

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))).

A261216 A(i,j) = rank (in A060117) of the composition of the i-th and the j-th permutation in table A060117, which lists all finite permutations.

Original entry on oeis.org

0, 1, 1, 2, 0, 2, 3, 5, 3, 3, 4, 4, 0, 2, 4, 5, 3, 1, 4, 5, 5, 6, 2, 5, 5, 3, 4, 6, 7, 7, 4, 1, 2, 1, 7, 7, 8, 6, 14, 0, 0, 0, 8, 6, 8, 9, 11, 15, 15, 1, 2, 9, 11, 9, 9, 10, 10, 12, 14, 22, 3, 10, 10, 6, 8, 10, 11, 9, 13, 16, 23, 23, 11, 9, 7, 10, 11, 11, 12, 8, 17, 17, 21, 22, 0, 8, 11, 11, 9, 10, 12, 13, 19, 16, 13, 20, 19, 1, 1, 10, 7, 8, 7, 13, 13, 14, 18, 8, 12, 18, 18, 2, 0, 12, 6, 6, 6, 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 of the permutation (in ordering used by table A060117) which is obtained by composing permutations p and q listed as the i-th and the j-th permutation in irregular table A060117 (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...
Equally, A(i,j) gives the rank in A060118 of the composition of the i-th and the j-th permutation in A060118, when convention is that "permutations act on the right".
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,  5,  4,  3,  2,  7,  6, 11, 10,  9,  8, 19, ...
   2,  3,  0,  1,  5,  4, 14, 15, 12, 13, 17, 16,  8, ...
   3,  2,  4,  5,  1,  0, 15, 14, 16, 17, 13, 12, 21, ...
   4,  5,  3,  2,  0,  1, 22, 23, 21, 20, 18, 19, 16, ...
   5,  4,  1,  0,  2,  3, 23, 22, 19, 18, 20, 21, 11, ...
   6,  7,  8,  9, 10, 11,  0,  1,  2,  3,  4,  5, 14, ...
   7,  6, 11, 10,  9,  8,  1,  0,  5,  4,  3,  2, 23, ...
   8,  9,  6,  7, 11, 10, 12, 13, 14, 15, 16, 17,  2, ...
   9,  8, 10, 11,  7,  6, 13, 12, 17, 16, 15, 14, 20, ...
  10, 11,  9,  8,  6,  7, 18, 19, 20, 21, 22, 23, 17, ...
  11, 10,  7,  6,  8,  9, 19, 18, 23, 22, 21, 20,  5, ...
  12, 13, 14, 15, 16, 17,  8,  9,  6,  7, 11, 10,  0, ...
  ...
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 A060117, 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 5th one in A060117, thus A(1,2) = 5.
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 A060117, 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: A261217.
Row 0 & Column 0: A001477 (identity permutation).
Row 1: A261218.
Column 1: A004442.
Main diagonal: A261219.
Cf. also A060117, A060118, A261096, A261097.
Permutations used in conjugation-formulas: A060119, A060120, A060125, A060126, A060127.

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

A055092 Order of each permutation given in reversed colexicographic ordering A055089, i.e., the least common multiple of their cycle lengths.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Apr 04 2000

nonn

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

Cf. A055089, A060131, A072411, A290095.

A055092(n) = count_permorder(convert(PermRevLexUnrank(j), 'disjcyc')).
count_permorder := proc(l) local c,t; t := 1; for c in l do t := ilcm(t,nops(c)); od; RETURN(t); end;
# Procedure PermRevLexUnrank given in A055089.

a(n) = A072411(A290095(n)) = A060131(A060126(n)). - Antti Karttunen, Dec 30 2017

Entry revised by Antti Karttunen, Dec 30 2017

cp's OEIS Frontend

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

A060132 Positions of the permutations which have the same rank in A055089 and A060117, i.e., the fixed points of permutations A060119 and A060126.

Views

Author

Keywords

Crossrefs

Programs

Maple

A060125 Self-inverse infinite permutation which shows the position of the inverse of each finite permutation in A060117 (or A060118) in the same sequence; or equally, the cross-indexing between A060117 and A060118.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

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

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A261216 A(i,j) = rank (in A060117) of the composition of the i-th and the j-th permutation in table A060117, which lists all finite permutations.

Views

Author

Keywords

Comments

Examples