A055092 -id:A055092 - 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

A072411 LCM of exponents in prime factorization of n, a(1) = 1.

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Jun 17 2002

The sums of the first 10^k terms, for k = 1, 2, ..., are 14, 168, 1779, 17959, 180665, 1808044, 18084622, 180856637, 1808585068, 18085891506, ... . Apparently, the asymptotic mean of this sequence is limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1.8085... . - Amiram Eldar, Sep 10 2022

			n = 288 = 2*2*2*2*2*3*3; lcm(5,2) = 10; Product(5,2) = 10, max(5,2) = 5;
n = 180 = 2*2*3*3*5; lcm(2,2,1) = 2; Product(2,2,1) = 4; max(2,2,1) = 2; it deviates both from maximum of exponents (A051903, for the first time at n=72), and product of exponents (A005361, for the first time at n=36).
For n = 36 = 2*2*3*3 = 2^2 * 3^2 we have a(36) = lcm(2,2) = 2.
For n = 72 = 2*2*2*3*3 = 2^3 * 3^2 we have a(72) = lcm(2,3) = 6.
For n = 144 = 2^4 * 3^2 we have a(144) = lcm(2,4) = 4.
For n = 360 = 2^3 * 3^2 * 5^1 we have a(360) = lcm(1,2,3) = 6.

Cf. A028234, A067029, A072412-A072414, A273058, A284569, A290103.
Similar sequences: A001222 (sum of exponents), A005361 (product), A051903 (maximal exponent), A051904 (minimal exponent), A052409 (gcd of exponents), A267115 (bitwise-and), A267116 (bitwise-or), A268387 (bitwise-xor).
Cf. also A055092, A060131.
Differs from A290107 for the first time at n=144.
After the initial term, differs from A157754 for the first time at n=360.

Table[LCM @@ Last /@ FactorInteger[n], {n, 2, 100}] (* Ray Chandler, Jan 24 2006 *)

a(n) = lcm(factor(n)[,2]); \\ Michel Marcus, Mar 25 2017

from sympy import lcm, factorint
def a(n):
    l=[]
    f=factorint(n)
    for i in f: l+=[f[i],]
    return lcm(l)
print([a(n) for n in range(1, 151)]) # Indranil Ghosh, Mar 25 2017

a(1) = 1; for n > 1, a(n) = lcm(A067029(n), a(A028234(n))). - Antti Karttunen, Aug 09 2016
From Antti Karttunen, Aug 22 2017: (Start)
a(n) = A284569(A156552(n)).
a(n) = A290103(A181819(n)).
a(A289625(n)) = A002322(n).
a(A290095(n)) = A055092(n).
a(A275725(n)) = A060131(n).
a(A260443(n)) = A277326(n).
a(A283477(n)) = A284002(n). (End)

a(1) = 1 prepended and the data section filled up to 120 terms by Antti Karttunen, Aug 09 2016

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)

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

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

A014489 Positions of involutions (permutations whose square is the identity) in reverse colexicographic order (A055089/A195663).

Original entry on oeis.org

0, 1, 2, 5, 6, 7, 14, 16, 21, 23, 24, 25, 26, 29, 54, 55, 60, 67, 80, 82, 86, 94, 105, 107, 111, 119, 120, 121, 122, 125, 126, 127, 134, 136, 141, 143, 264, 265, 266, 269, 288, 289, 314, 316, 339, 341, 390, 391, 396, 403, 414, 415, 444, 450, 469

Offset: 0

Wouter Meeussen

nonn

Robert Israel, Table of n, a(n) for n = 0..3996

Positions of zeros in A261099.
From a(1)=1 onward also positions of 2's in A055092.
Subsequences: A060112, A064640.
Cf. A055089, A195663.
Cf. also A261220.

N:= 100: # to get a(0) to a(N)
M:= 0: A[0]:= 0: count:= 0:
for m from 2 while count < N do
  P:= remove(t -> t[1]=1, combinat:-permute(m));
  P:= map(t -> ListTools:-Reverse(subs([seq(i=m+1-i,i=1..m)],t)),P);
  R:= select(t -> max(map(nops,convert(P[t],disjcyc))) = 2, [$1..nops(P)]);
  for r in R do
     count:= count+1;
     A[count]:= r+M;
     if count = N then break fi;
  od:
  M:= M + nops(P);
od:
seq(A[i],i=0..count); # Robert Israel, Oct 28 2015

Name changed by Antti Karttunen, Aug 30 2015

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

A072411 LCM of exponents in prime factorization of n, a(1) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

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

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

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

A014489 Positions of involutions (permutations whose square is the identity) in reverse colexicographic order (A055089/A195663).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Extensions