A060125 -id:A060125 - cp's OEIS frontend

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.

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

A065163 Maximal orbit size in the symmetric group partitioned by the upper records version of the Foata transform (i.e., a(n) is the maximum cycle length found in the corresponding permutations A065181-A065184 in range [0, n!-1]).

Original entry on oeis.org

1, 1, 3, 7, 25, 216, 963, 23435, 92225, 2729205, 17313348, 182553725, 4235194171

Offset: 1

Antti Karttunen, Oct 19 2001

Note: the number of fixed terms in each successive range [0, n!-1] is given by A000045(n+1) (Fibonacci numbers) and the corresponding positions by A060112. (Foata transform fixes a permutation only if it is composed of disjoint adjacent transpositions.)

This version of the Foata transform is one of several. This map takes a permutation s in S_n with k cycles to a permutation t in S_n with k upper records, i.e., k indices i for which t(i) > max{t(j): j < i}. - Theodore Zhu, Aug 15 2014

Cf. A065161, A065162.

For the requisite Maple procedures see sequences A057502, A057542, A060117, A060125.

FoataPermutationCycleCounts_Lengths_and_LCM := proc(upto_n) local u,n,a,b,i,f; a := []; b := []; f := 1; for i from 0 to upto_n! -1 do b := [op(b),1+PermRank3R(Foata(PermUnrank3R(i)))]; if((f - 1) = i) then a := [op(a),[CountCycles(b), CycleLengths1(b), CyclesLCM(b)]]; print (a); f := f*(nops(a)+1); fi; od; RETURN(a); end;
lcmlist := proc(a) local z,e; z := 1; for e in a do z := ilcm(z,e); od; RETURN(z); end;
CyclesLCM := b -> lcmlist(map(nops,convert(b,'disjcyc')));

More terms from Theodore Zhu, Aug 15 2014

A065184 Permutation of nonnegative integers produced when the finite permutations listed by A060117 are subjected to the left-right maxima variant of Foata's transformation. Inverse of A065183.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 19 2001

nonn

Index entries for sequences that are permutations of the natural numbers

A065161-A065163 give cycle counts and max lengths. Cf. also A065181, A065182 for Maple procedure Foata and A060117 for PermUnrank3R and A060125 for PermRank3R.

[seq(PermRank3R(Foata(PermUnrank3R(j))),j=0..119)];

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

Original entry on oeis.org

0, 1, 1, 2, 0, 2, 3, 3, 5, 3, 4, 2, 0, 4, 4, 5, 5, 4, 1, 3, 5, 6, 4, 3, 5, 5, 2, 6, 7, 7, 1, 2, 1, 4, 7, 7, 8, 6, 8, 0, 0, 0, 14, 6, 8, 9, 9, 11, 9, 2, 1, 15, 15, 11, 9, 10, 8, 6, 10, 10, 3, 22, 14, 12, 10, 10, 11, 11, 10, 7, 9, 11, 23, 23, 16, 13, 9, 11, 12, 10, 9, 11, 11, 8, 0, 22, 21, 17, 17, 8, 12, 13, 13, 7, 8, 7, 10, 1, 1, 19, 20, 13, 16, 19, 13, 14, 12, 14, 6, 6, 6, 12, 0, 2, 18, 18, 12, 8, 18, 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 A060118) 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 A060118 (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 A060117 of the composition of the i-th and the j-th permutation in A060117, 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,  3,  2,  5,  4,  7,  6,  9,  8, 11, 10, 13, ...
   2,  5,  0,  4,  3,  1,  8, 11,  6, 10,  9,  7, 14, ...
   3,  4,  1,  5,  2,  0,  9, 10,  7, 11,  8,  6, 15, ...
   4,  3,  5,  1,  0,  2, 10,  9, 11,  7,  6,  8, 16, ...
   5,  2,  4,  0,  1,  3, 11,  8, 10,  6,  7,  9, 17, ...
   6,  7, 14, 15, 22, 23,  0,  1, 12, 13, 18, 19,  8, ...
   7,  6, 15, 14, 23, 22,  1,  0, 13, 12, 19, 18,  9, ...
   8, 11, 12, 16, 21, 19,  2,  5, 14, 17, 20, 23,  6, ...
   9, 10, 13, 17, 20, 18,  3,  4, 15, 16, 21, 22,  7, ...
  10,  9, 17, 13, 18, 20,  4,  3, 16, 15, 22, 21, 11, ...
  11,  8, 16, 12, 19, 21,  5,  2, 17, 14, 23, 20, 10, ...
  12, 19,  8, 21, 16, 11, 14, 23,  2, 20, 17,  5,  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 A060118, 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 3rd one in A060118, thus A(1,2) = 3.
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 5th one in A060118, thus A(2,1) = 5.

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

Transpose: A261216.
Row 0 & Column 0: A001477 (identity permutation)
Row 1: A004442.
Column 1: A261218.
Main diagonal: A261219.
Cf. also A060117, A060118, A261096, A261097.
Cf. also A089839.
Permutations used in conjugation-formulas: A060119, A060120, A060125, A060126, A060127.

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

A060500 a(n) = number of drops in the n-th permutation of list A060118; the average of digits (where "digits" may eventually obtain also any values > 9) in each siteswap pattern A060496(n).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Mar 22 2001

nonn

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

Cf. A060125, A060129, A060501, A060502, A275849, A275851.

A060500 := avg(Perm2SiteSwap1(PermUnrank3R(n)));
# PermUnrank3R(r) gives the permutation with rank r in list A060117:
PermUnrank3R := proc(r) local n; n := nops(factorial_base(r)); convert(PermUnrank3Raux(n+1, r, []), 'permlist', 1+(((r+2) mod (r+1))*n)); end;
PermUnrank3Raux := proc(n, r, p) local s; if(0 = r) then RETURN(p); else s := floor(r/((n-1)!)); RETURN(PermUnrank3Raux(n-1, r-(s*((n-1)!)), permul(p, [[n, n-s]]))); fi; end;
Perm2SiteSwap1 := proc(p) local ip, n, i, a; n := nops(p); ip := convert(invperm(convert(p, 'disjcyc')), 'permlist', n); a := []; for i from 1 to n do a := [op(a), ((ip[i]-i) mod n)]; od; RETURN(a); end;
avg := a -> (convert(a,`+`)/nops(a));

(define (A060500 n) (let ((s (+ 1 (A084558 n))) (p (A060118permvec-short n))) (let loop ((d 0) (i 1)) (if (> i s) d (loop (+ d (if (< (vector-ref p (- i 1)) i) 1 0)) (+ 1 i))))))
(define (A060118permvec-short rank) (permute-A060118 (make-initialized-vector (+ 1 (A084558 rank)) 1+) (+ 1 (A084558 rank)) rank))
(define (permute-A060118 elems size permrank) (let ((p (vector-head elems size))) (let unrankA060118 ((r permrank) (i 1)) (cond ((zero? r) p) (else (let* ((j (1+ i)) (m (modulo r j))) (cond ((not (zero? m)) (let ((org-i (vector-ref p i))) (vector-set! p i (vector-ref p (- i m))) (vector-set! p (- i m) org-i)))) (unrankA060118 (/ (- r m) j) j)))))))

From Antti Karttunen, Aug 18 2016: (Start)
The following formula reflects the original definition of computing the average, with a few unnecessary steps eliminated:
a(n) = 1/s * Sum_{i=1..s} ((i-p[i]) modulo s), where p is the permutation of rank n as ordered in the list A060117, and s is its size (the number of its elements) computed as s = 1+A084558(n).
a(n) = 1/s * Sum_{i=1..s} ((p[i]-i) modulo s). [If inverse permutations from list A060118 are used, then we just flip the order of difference that is used in the first formula].
a(n) = Sum_{i=1..s} [p[i]A060502 for the proof].
a(n) = A060502(A060125(n)).
a(n) = A060129(n) - A060502(n).
a(n) = A060501(n) - A275851(n) = 1 + A275849(n) - A275851(n).
(End)

Maple code collected together, alternative definition and new formulas added by Antti Karttunen, Aug 24 2016

A065183 Permutation of nonnegative integers produced when the finite permutations listed by A060117 are subjected to the inverse of (variant of) Foata's transformation. Inverse of A065184.

Original entry on oeis.org

0, 1, 2, 4, 5, 3, 6, 7, 12, 20, 19, 17, 14, 21, 8, 10, 15, 18, 23, 16, 22, 13, 11, 9, 24, 25, 26, 28, 29, 27, 48, 49, 78, 108, 103, 91, 74, 111, 62, 69, 75, 104, 101, 94, 100, 83, 71, 64, 54, 55, 80, 109, 107, 90, 30, 31, 36, 44, 43, 41, 56, 58, 72, 110, 106, 77, 59, 57, 81

Offset: 0

Antti Karttunen, Oct 19 2001

nonn

Index entries for sequences that are permutations of the natural numbers

A065161-A065163 give cycle counts and max lengths. Cf. also A065182, A065181 for Maple procedure FoataInv and A060117 for PermUnrank3R and A060125 for PermRank3R.

[seq(PermRank3R(FoataInv(PermUnrank3R(j))),j=0..119)];

A064638 Positions of non-crossing fixed-point-free involutions encoded by A014486 in A055089. Permutation of A064640.

Original entry on oeis.org

0, 1, 7, 23, 127, 415, 143, 659, 719, 5167, 16687, 5455, 26815, 28495, 5183, 16703, 5699, 36899, 38579, 5759, 36959, 40031, 40319, 368047, 1174447, 379567, 1901647, 1992367, 368335, 1174735, 389695, 2627455, 2718175, 391375, 2629135, 2799055

Offset: 0

Antti Karttunen, Oct 02 2001

nonn

Maple procedure binexp2pars given in A057501, permul in A060125.

map(PermRevLexRank,map(NonCrossingTranspos, A014486));
NonCrossingTranspos := n -> convert(NonCrossingTransposAux(binexp2pars(n),1),'permlist',binwidth(n));
NonCrossingTransposAux := proc(s,ii) local e,p,i,j; i := ii; p := []; for e in s do p := permul(p,NonCrossingTransposAux(e,i+1)); j := i+CountParens(e)+1; p := permul(p,[[i,j]]); i := j+1; od; RETURN(p); end;
CountParens := proc(s) local e,k; if(0 = nops(s)) then RETURN(0); fi; e := 0; for k in s do e := e+2+CountParens(k); od; RETURN(e); end;

cp's OEIS Frontend

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

Links

Crossrefs

Formula

A065163 Maximal orbit size in the symmetric group partitioned by the upper records version of the Foata transform (i.e., a(n) is the maximum cycle length found in the corresponding permutations A065181-A065184 in range [0, n!-1]).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Extensions

A065184 Permutation of nonnegative integers produced when the finite permutations listed by A060117 are subjected to the left-right maxima variant of Foata's transformation. Inverse of A065183.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A060500 a(n) = number of drops in the n-th permutation of list A060118; the average of digits (where "digits" may eventually obtain also any values > 9) in each siteswap pattern A060496(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Scheme

Formula

Extensions

A065183 Permutation of nonnegative integers produced when the finite permutations listed by A060117 are subjected to the inverse of (variant of) Foata's transformation. Inverse of A065184.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A064638 Positions of non-crossing fixed-point-free involutions encoded by A014486 in A055089. Permutation of A064640.

Views

Author

Keywords

Crossrefs

Programs

Maple