A060132 -id:A060132 - cp's OEIS frontend

A064637 Setwise difference of A060132 and A059590. Those terms of A060132 which are not representable as a sum of distinct factorials.

16, 17, 40, 41, 60, 61, 62, 63, 136, 137, 160, 161, 180, 181, 182, 183, 288, 289, 290, 291, 294, 295, 296, 297, 304, 305, 316, 317, 450, 451, 452, 453, 736, 737, 760, 761, 780, 781, 782, 783, 856, 857, 880, 881, 900, 901, 902, 903, 1008, 1009, 1010, 1011

Offset: 0

Antti Karttunen, Oct 02 2001

nonn

16 is included, as 16 = 220 in factorial base and by following the algorithm PermRevLexUnrankAMSD in A055089 we get the composition (2 3)(3 4) (1 2)(2 3) which, although consisting of different transpositions, is equal to the composition (4 2)(3 1) = 3412 produced by algorithm PermUnrank3R at A060117.

A064637 := list_diff(A060132, A059590),

Cf. A064477.

list_diff := proc(a,b) local c,e; c := []; for e in a do if(not member(e,b)) then c := [op(c),e]; fi; od; RETURN(c); end;

A055089 List of all finite permutations in reversed colexicographic ordering.

Original entry on oeis.org

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

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

Original entry on oeis.org

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)

A059590 Numbers obtained by reinterpreting base-2 representation of n in the factorial base: a(n) = Sum_{k>=0} A030308(n,k)*A000142(k+1).

Original entry on oeis.org

0, 1, 2, 3, 6, 7, 8, 9, 24, 25, 26, 27, 30, 31, 32, 33, 120, 121, 122, 123, 126, 127, 128, 129, 144, 145, 146, 147, 150, 151, 152, 153, 720, 721, 722, 723, 726, 727, 728, 729, 744, 745, 746, 747, 750, 751, 752, 753, 840, 841, 842, 843, 846, 847, 848, 849, 864, 865

Offset: 0

Henry Bottomley, Jan 24 2001

Numbers that are sums of distinct factorials (0! and 1! not treated as distinct).
Complement of A115945; A115944(a(n)) > 0; A115647 is a subsequence. - Reinhard Zumkeller, Feb 02 2006
A115944(a(n)) = 1. - Reinhard Zumkeller, Dec 04 2011
From Tilman Piesk, Jun 04 2012: (Start)
The inversion vector (compare A007623) of finite permutation a(n) (compare A055089, A195663) has only zeros and ones. Interpreted as a binary number it is 2*n (or n when the inversion vector is defined without the leading 0).
The inversion set of finite permutation a(n) interpreted as a binary number (compare A211362) is A211364(n).
(End)

			128 is in the sequence since 5! + 3! + 2! = 128.
a(22) = 128. a(22) = a(6) + (1 + floor(log(16) / log(2)))! = 8 + 5! = 128. Also, 22 = 10110_2. Therefore, a(22) = 1 * 5! + 0 * 4! + 1 * 3! + 1 + 2! + 0 * 0! = 128. - _David A. Corneth_, Aug 21 2016

Reinhard Zumkeller (terms 0..500) & Antti Karttunen, Table of n, a(n) for n = 0..8191
Index entries for sequences related to factorial base representation
Index entries for sequences related to factorial numbers

Cf. A007088, A007623, A014597, A051760, A051761, A059589.
Indices of zeros in A257684.
Cf. A275736 (left inverse).
Cf. A025494, A060112 (subsequences).
Cf. A153880, A225901.
Subsequence of A060132, A256450 and A275804.
Other sequences that are built by replacing 2^k in the binary representation with other numbers: A029931 (naturals), A089625 (primes), A022290 (Fibonacci), A197433 (Catalans), A276091 (n*n!), A275959 ((2n)!/2). Cf. also A276082 & A276083.

import Data.List (elemIndices)
a059590 n = a059590_list !! n
a059590_list = elemIndices 1 $ map a115944 [0..]
-- Reinhard Zumkeller, Dec 04 2011

[seq(bin2facbase(j),j=0..64)]; bin2facbase := proc(n) local i; add((floor(n/(2^i)) mod 2)*((i+1)!),i=0..floor_log_2(n)); end;
floor_log_2 := proc(n) local nn,i; nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi; nn := floor(nn/2); od; end;
# next Maple program:
a:= n-> (l-> add(l[j]*j!, j=1..nops(l)))(Bits[Split](n)):
seq(a(n), n=0..57);  # Alois P. Heinz, Aug 12 2025

a[n_] :=  Reverse[id = IntegerDigits[n, 2]].Range[Length[id]]!; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Jun 19 2012, after Philippe Deléham *)

a(n) = if(n>0, a(n-msb(n)) + (1+logint(n,2))!, 0)
msb(n) = 2^#binary(n)>>1
{my(b = binary(n)); sum(i=1,#b,b[i]*(#b+1-i)!)} \\ David A. Corneth, Aug 21 2016

def facbase(k, f):
    return sum(f[i] for i, bi in enumerate(bin(k)[2:][::-1]) if bi == "1")
def auptoN(N): # terms up to N factorial-base digits; 13 generates b-file
    f = [factorial(i) for i in range(1, N+1)]
    return list(facbase(k, f) for k in range(2**N))
print(auptoN(5)) # Michael S. Branicky, Oct 15 2022

G.f. 1/(1-x) * Sum_{k>=0} (k+1)!*x^2^k/(1+x^2^k). - Ralf Stephan, Jun 24 2003
a(n) = Sum_{k>=0} A030308(n,k)*A000142(k+1). - Philippe Deléham, Oct 15 2011
From Antti Karttunen, Aug 19 2016: (Start)
a(0) = 0, a(2n) = A153880(a(n)), a(2n+1) = 1+A153880(a(n)).
a(n) = A225901(A276091(n)).
a(n) = A276075(A019565(n)).
a(A275727(n)) = A276008(n).
A275736(a(n)) = n.
A276076(a(n)) = A019565(n).
A007623(a(n)) = A007088(n).
(End)
a(n) = a(n - mbs(n)) + (1 + floor(log(n) / log(2)))!. - David A. Corneth, Aug 21 2016

Name changed (to emphasize the functional nature of the sequence) with the old definition moved to the comments by Antti Karttunen, Aug 21 2016

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

Original entry on oeis.org

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

cp's OEIS Frontend

A064637 Setwise difference of A060132 and A059590. Those terms of A060132 which are not representable as a sum of distinct factorials.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

A055089 List of all finite permutations in reversed colexicographic ordering.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A059590 Numbers obtained by reinterpreting base-2 representation of n in the factorial base: a(n) = Sum_{k>=0} A030308(n,k)*A000142(k+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

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

A060133 Positions of the permutations which have the same rank in A055089 and A060118, i.e., the fixed points of permutations A060120 and A060127.

Views

Author

Keywords

Crossrefs

Programs

Maple