|
| |
|
|
A034968
|
|
Minimal number of factorials which add to n.
|
|
18
|
|
|
|
0, 1, 1, 2, 2, 3, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 4, 5, 5, 6, 6, 7, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 3, 4, 4, 5, 5, 6, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 6, 7, 7, 8, 8, 9, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Equivalently, sum of digits when n is written in factorial base (A007623).
Equivalently, a(0)...a(n!-1) give the total number of inversions of the permutations of n elements in lexicographic order (the factorial numbers in rising base are the inversion tables of the permutations and their sum of digits give the total number of inversions, see example and the Fxtbook link). [Joerg Arndt, Jun 17 2011]
Also minimum number of adjacent transpositions needed to produce each permutation in the list A055089 (or number of swappings needed to bubble sort each such permutation).
|
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 0..10000
Joerg Arndt, Fxtbook, fig.10-1.B on p.234
|
|
|
FORMULA
|
a(n) = n-sum(i>=2, (i-1)*floor(n/i!)). - Benoit Cloitre, Aug 26 2003
G.f.: 1/(1-x)*Sum_{k>0} (Sum_{i=1..k} i*x^(i*k!))/(Sum_{i=0..k} x^(i*k!)). - Franklin T. Adams-Watters, May 13 2009
|
|
|
EXAMPLE
|
a(205) = a(1!*1+3!*2+4!*3+5!*1) = 1+2+3+1 = 6.
From Joerg Arndt, Jun 17 2011: (Start)
n: permutation inv. table a(n) cycles
0: [ 0 1 2 3 ] [ 0 0 0 ] 0 (0) (1) (2) (3)
1: [ 0 1 3 2 ] [ 0 0 1 ] 1 (0) (1) (2, 3)
2: [ 0 2 1 3 ] [ 0 1 0 ] 1 (0) (1, 2) (3)
3: [ 0 2 3 1 ] [ 0 1 1 ] 2 (0) (1, 2, 3)
4: [ 0 3 1 2 ] [ 0 2 0 ] 2 (0) (1, 3, 2)
5: [ 0 3 2 1 ] [ 0 2 1 ] 3 (0) (1, 3) (2)
6: [ 1 0 2 3 ] [ 1 0 0 ] 1 (0, 1) (2) (3)
7: [ 1 0 3 2 ] [ 1 0 1 ] 2 (0, 1) (2, 3)
8: [ 1 2 0 3 ] [ 1 1 0 ] 2 (0, 1, 2) (3)
9: [ 1 2 3 0 ] [ 1 1 1 ] 3 (0, 1, 2, 3)
10: [ 1 3 0 2 ] [ 1 2 0 ] 3 (0, 1, 3, 2)
11: [ 1 3 2 0 ] [ 1 2 1 ] 4 (0, 1, 3) (2)
12: [ 2 0 1 3 ] [ 2 0 0 ] 2 (0, 2, 1) (3)
13: [ 2 0 3 1 ] [ 2 0 1 ] 3 (0, 2, 3, 1)
14: [ 2 1 0 3 ] [ 2 1 0 ] 3 (0, 2) (1) (3)
15: [ 2 1 3 0 ] [ 2 1 1 ] 4 (0, 2, 3) (1)
16: [ 2 3 0 1 ] [ 2 2 0 ] 4 (0, 2) (1, 3)
17: [ 2 3 1 0 ] [ 2 2 1 ] 5 (0, 2, 1, 3)
18: [ 3 0 1 2 ] [ 3 0 0 ] 3 (0, 3, 2, 1)
19: [ 3 0 2 1 ] [ 3 0 1 ] 4 (0, 3, 1) (2)
20: [ 3 1 0 2 ] [ 3 1 0 ] 4 (0, 3, 2) (1)
21: [ 3 1 2 0 ] [ 3 1 1 ] 5 (0, 3) (1) (2)
22: [ 3 2 0 1 ] [ 3 2 0 ] 5 (0, 3, 1, 2)
23: [ 3 2 1 0 ] [ 3 2 1 ] 6 (0, 3) (1, 2)
(End)
|
|
|
MAPLE
|
[seq(convert(fac_base(j), `+`), j=0..119)]; # fac_base and PermRevLexUnrank given in A055089. Perm2InversionVector in A064039
Or alternatively: [seq(convert(Perm2InversionVector(PermRevLexUnrank(j)), `+`), j=0..119)];
# third Maple program:
b:= proc(n, i) local q;
`if`(n=0, 0, b(irem(n, i!, 'q'), i-1)+q)
end:
a:= proc(n) local k;
for k while k!<n do od; b(n, k)
end:
seq (a(n), n=0..200); # Alois P. Heinz, Nov 15 2012
|
|
|
PROG
|
(PARI) a(n)=local(k, r); k=2; r=0; while(n>0, r+=n%k; n\=k; k++); r [From Franklin T. Adams-Watters, May 13 2009]
|
|
|
CROSSREFS
|
Partial sums of first n! terms: A001809. See A055091 for the minimum number of any transpositions. A034968[A056019[n]] = A034968[n] for all n.
Sequence in context: A092331 A200747 A089293 * A054707 A166269 A181648
Adjacent sequences: A034965 A034966 A034967 * A034969 A034970 A034971
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Erich Friedman
|
|
|
EXTENSIONS
|
Additional comments from Antti Karttunen, Aug 23, 2001.
|
|
|
STATUS
|
approved
|
| |
|
|
