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
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..10000
F. T. Adams-Watters and F. Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS 12 (2009) 09.5.6.
Joerg Arndt, Matters Computational (The Fxtbook), fig.10-1.B on p.234.
Tyler Ball, Joanne Beckford, Paul Dalenberg, Tom Edgar, and Tina Rajabi, Some Combinatorics of Factorial Base Representations, J. Int. Seq., Vol. 23 (2020), Article 20.3.3.
FindStat - Combinatorial Statistic Finder, The number of inversions of a permutation
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
From Antti Karttunen, Aug 29 2016: (Start)
Other identities. For all n >= 0:
a(A056019(n)) = a(n).
A219651(n) = n - a(n).
(End)
EXAMPLE
a(205) = a(1!*1 + 3!*2 + 4!*3 + 5!*1) = 1+2+3+1 = 7. [corrected by Shin-Fu Tsai, Mar 23 2021]
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
MATHEMATICA
a[n_] := Module[{s=0, i=2, k=n}, While[k > 0, k = Floor[n/i!]; s = s + (i-1)*k; i++]; n-s]; Table[a[n], {n, 0, 105}] (* Jean-François Alcover, Nov 06 2013, after Benoit Cloitre *)
PROG
(PARI) a(n)=local(k, r); k=2; r=0; while(n>0, r+=n%k; n\=k; k++); r \\ Franklin T. Adams-Watters, May 13 2009
(Scheme)
(define (A034968 n) (let loop ((n n) (i 2) (s 0)) (cond ((zero? n) s) (else (loop (quotient n i) (+ 1 i) (+ s (remainder n i)))))))
;; Antti Karttunen, Aug 29 2016
(Python)
def a(n):
k=2
r=0
while n>0:
r+=n%k
n=n//k
k+=1
return r
print([a(n) for n in range(201)]) # Indranil Ghosh, Jun 19 2017, after PARI program
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
Additional comments from Antti Karttunen, Aug 23 2001
STATUS
approved