A060118 -id:A060118 - cp's OEIS frontend

A060117 A list of all finite permutations in "PermUnrank3R" ordering. (Inverses of the permutations of A060118.)

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

Offset: 0

Antti Karttunen, Mar 02 2001

PermUnrank3R and PermUnrank3L are slight modifications of unrank2 algorithm presented in Myrvold-Ruskey article.

			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; 3,2,1; 2,3,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 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,...
3,2,1/4,5,6,7,8,9,...
2,3,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,...

W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time, Inform. Process. Lett. 79 (2001), no. 6, 281-284.

A060119 = Positions of these permutations in the "canonical list" A055089 (where also the rest of procedures can be found). A060118 gives position of the inverse permutation of each and A065183 positions after Foata transform.
Inversion vectors: A064039.
Cf. A060125, A060128, A060129, A060130, A060131, A060132, A060495.

with(group); permul := (a,b) -> mulperms(b,a); 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;

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

A060130 Number of nonzero digits in factorial base representation (A007623) of n; minimum number of transpositions needed to compose each permutation in the lists A060117 & A060118.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Mar 02 2001

nonn

			19 = 3*(3!) + 0*(2!) + 1*(1!), thus it is written as "301" in factorial base (A007623). The count of nonzero digits in that representation is 2, so a(19) = 2.

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

Cf. A007623, A034968, A055091, A060117, A060118, A060128, A060129, A060131, A060502, A257687, A275734, A275735, A276076.
Cf. A227130 (positions of even terms), A227132 (of odd terms).
Cf. also A225901, A232094, A257694, A257695.
The topmost row and the leftmost column in array A230415, the left edge of triangle A230417.
Differs from similar A267263 for the first time at n=30.

A060130(n) = count_nonfixed(convert(PermUnrank3R(n), 'disjcyc'))-nops(convert(PermUnrank3R(n), 'disjcyc')) or nops(fac_base(n))-nops(positions(0, fac_base(n)))
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;
count_nonfixed := l -> convert(map(nops, l), `+`);
positions := proc(e, ll) local a, k, l, m; l := ll; m := 1; a := []; while(member(e, l[m..nops(l)], 'k')) do a := [op(a), (k+m-1)]; m := k+m; od; RETURN(a); end;
# For procedure PermUnrank3R see A060117

Block[{nn = 105, r}, r = MixedRadix[Reverse@ Range[2, -1 + SelectFirst[Range@ 12, #! > nn &]]]; Array[Count[IntegerDigits[#, r], k_ /; k > 0] &, nn, 0]] (* Michael De Vlieger, Dec 30 2017 *)

(define (A060130 n) (let loop ((n n) (i 2) (s 0)) (cond ((zero? n) s) (else (loop (quotient n i) (+ 1 i) (+ s (if (zero? (remainder n i)) 0 1)))))))
;; Two other implementations, that use memoization-macro definec:
(definec (A060130 n) (if (zero? n) n (+ 1 (A060130 (A257687 n)))))
(definec (A060130 n) (if (zero? n) n (+ (A257511 n) (A060130 (A257684 n)))))
;; Antti Karttunen, Dec 30 2017

a(0) = 0; for n > 0, a(n) = 1 + a(A257687(n)).
a(0) = 0; for n > 0, a(n) = A257511(n) + a(A257684(n)).
a(n) = A060129(n) - A060128(n).
a(n) = A084558(n) - A257510(n).
a(n) = A275946(n) + A275962(n).
a(n) = A275948(n) + A275964(n).
a(n) = A055091(A060119(n)).
a(n) = A069010(A277012(n)) = A000120(A275727(n)).
a(n) = A001221(A275733(n)) = A001222(A275733(n)).
a(n) = A001222(A275734(n)) = A001222(A275735(n)) = A001221(A276076(n)).
a(n) = A046660(A275725(n)).
a(A225901(n)) = a(n).
A257511(n) <= a(n) <= A034968(n).
A275806(n) <= a(n).
a(A275804(n)) = A060502(A275804(n)). [A275804 gives all the positions where this coincides with A060502.]
a(A276091(n)) = A260736(A276091(n)). [A276091 gives all the positions where this coincides with A260736.]

Example-section added, name edited, the old Maple-code moved away from the formula-section, and replaced with all the new formulas by Antti Karttunen, Dec 30 2017

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

A275725 a(n) = A275723(A002110(1+A084558(n)), n); prime factorization encodings of cycle-polynomials computed for finite permutations listed in the order that is used in tables A060117 / A060118.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Aug 09 2016

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 tables A060117 or A060118. See the examples.

			Consider the first eight permutations (indices 0-7) listed in A060117:
  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]
  3,2,1 [One transposition jumping over a fixed element, a(4) = 2^2 * 3^1 = 12]
  2,3,1 [One 3-cycle, thus a(5) = 2^3 = 8]
  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]
and also the seventeenth one at n=16 [A007623(16)=220] where we have:
  3,4,1,2 [Two 2-cycles crossed, thus a(16) = 2^2 * 3^2 = 36].

Antti Karttunen, Table of n, a(n) for n = 0..40319
Indranil Ghosh, Python program for computing this sequence
Index entries for sequences related to factorial base representation

Cf. A000040, A001222, A001221, A002110, A007814, A046660, A048675, A051903, A056169, A056170, A084558, A243054, A257510, A275723, A275803, A275832.
Cf. A275807 (terms divided by 2).
Cf. also A060129, A060128, A060130, A060131, A072411, A275726, A275812, A275851.
Cf. also A275733, A275734, A275735 for other such prime factorization encodings of A060117/A060118-related polynomials.

(define (A275725 n) (A275723bi (A002110 (+ 1 (A084558 n))) n)) ;; Code for A275723bi given in A275723.

a(n) = A275723(A002110(1+A084558(n)), n).
Other identities:
A001221(a(n)) = 1+A257510(n) (for all n >= 1).
A001222(a(n)) = 1+A084558(n).
A007814(a(n)) = A275832(n).
A048675(a(n)) = A275726(n).
A051903(a(n)) = A275803(n).
A056169(a(n)) = A275851(n).
A046660(a(n)) = A060130(n).
A072411(a(n)) = A060131(n).
A056170(a(n)) = A060128(n).
A275812(a(n)) = A060129(n).
a(n!) = 2 * A243054(n) = A000040(n)*A002110(n) for all n >= 1.

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

A060131 a(n) = A072411(A275725(n)); order of each permutation listed in tables A060117 and A060118, i.e., the least common multiple of the cycle sizes.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 2, 2, 3, 4, 3, 4, 2, 3, 3, 4, 2, 4, 2, 3, 2, 4, 3, 4, 2, 2, 2, 6, 2, 6, 3, 6, 4, 5, 4, 5, 3, 4, 4, 5, 6, 5, 3, 4, 6, 5, 4, 5, 2, 2, 3, 4, 3, 4, 3, 6, 4, 5, 4, 5, 2, 6, 4, 5, 6, 5, 2, 6, 6, 5, 4, 5, 2, 3, 3, 4, 2, 4, 2, 6, 4, 5, 6, 5, 3, 4, 4, 5, 6, 5, 2, 4, 6, 5, 6, 5, 2, 3, 2, 4, 3, 4, 2, 6, 6, 5, 4, 5, 2, 4, 6, 5, 6, 5, 3, 4, 6, 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 lcm's

Cf. A055092, A060117, A060118, A060120, A072411, A275725.
Cf. A261220 (gives the positions of 1 and 2's).
Cf. A275813 (indices of odd terms), A275814 (indices of even terms).

(define (A060131 n) (A072411 (A275725 n)))

From Antti Karttunen, Aug 09 2016: (Start)
a(n) = A072411(A275725(n)).
a(n) = A055092(A060120(n)).
(End)

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)

A060128 a(n) is the number of disjoint cycles (excluding 1-cycles, i.e., fixed elements) in the n-th permutation of A060117 and A060118.

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, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 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. A055090, A056170, A060118, A060120, A060129, A060130, A275725, A278225, A276004.

Cf. A276005 (positions where coincides with A060502).

A060128(n) = nops(convert(PermUnrank3L(n), 'disjcyc')); # Code for function PermUnrank3L given in A060118.

a(n) = A060129(n) - A060130(n).
From Antti Karttunen, Aug 07 2017: (Start)
a(n) = A056170(A275725(n)).
a(n) = A055090(A060120(n)).
a(n) = A060502(n) - A276004(n).
(End)

A261220 Ranks of involutions in permutation orderings A060117 and A060118.

Original entry on oeis.org

0, 1, 2, 4, 6, 7, 12, 16, 18, 20, 24, 25, 26, 28, 48, 49, 60, 66, 72, 76, 78, 90, 96, 98, 102, 108, 120, 121, 122, 124, 126, 127, 132, 136, 138, 140, 240, 241, 242, 244, 288, 289, 312, 316, 336, 338, 360, 361, 372, 378, 384, 385, 432, 450, 456, 468, 480, 484, 486, 498, 504, 508, 528, 546, 576, 582, 600, 602, 606, 612, 624, 626, 648, 660, 672, 678, 720, 721

Offset: 0

Antti Karttunen, Aug 26 2015

From Antti Karttunen, Aug 17 2016: (Start)
Intersection of A275804 and A276005. In other words, these are numbers in whose factorial base representation (A007623, see A260743) there does not exist any such pair of nonzero digits d_i and d_j in positions i and j that either (i - d_i) = j or (i - d_i) = (j - d_j) would hold. Here one-based indexing is used so that the least significant digit at right is in position 1.
(End)

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

Intersection of A275804 and A276005.
Same sequence shown in factorial base: A260743.
Cf. A060117, A060118, A275947, A276007.
Positions of zeros in A261219.
Positions of 1 and 2's in A060131 and A275803.
Subsequence: A060112.
Cf. also A014489.

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

cp's OEIS Frontend

A060117 A list of all finite permutations in "PermUnrank3R" ordering. (Inverses of the permutations of A060118.)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A060130 Number of nonzero digits in factorial base representation (A007623) of n; minimum number of transpositions needed to compose each permutation in the lists A060117 & A060118.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Scheme

Formula

Extensions

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

A275725 a(n) = A275723(A002110(1+A084558(n)), n); prime factorization encodings of cycle-polynomials computed for finite permutations listed in the order that is used in tables A060117 / A060118.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

A060131 a(n) = A072411(A275725(n)); order of each permutation listed in tables A060117 and A060118, i.e., the least common multiple of the cycle sizes.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

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

A060128 a(n) is the number of disjoint cycles (excluding 1-cycles, i.e., fixed elements) in the n-th permutation of A060117 and A060118.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A261220 Ranks of involutions in permutation orderings A060117 and A060118.

Views

Author