login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A034968 Minimal number of factorials which add to n. 34
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, Matters Computational (The Fxtbook), fig.10-1.B on p.234

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

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

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

Cf. A139365

Sequence in context: A092331 A200747 A089293 * A236920 A054707 A226743

Adjacent sequences:  A034965 A034966 A034967 * A034969 A034970 A034971

KEYWORD

nonn

AUTHOR

Erich Friedman

EXTENSIONS

Additional comments from Antti Karttunen, Aug 23, 2001.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 22 20:35 EST 2014. Contains 252372 sequences.