A096770 a(1) = 1; for n >= 1, replace each part, with repetitions, of every part k in each partition of n with a(k), then take the sum to get a(n+1).

1, 1, 3, 8, 21, 51, 127, 303, 734, 1751, 4200, 10004, 23918, 56981, 135958, 323996, 772530, 1840993, 4388456, 10458354, 24926754, 59405383, 141581236, 337417607, 804153140, 1916469872, 4567399008, 10885108498, 25941679513, 61824709789

Offset

1,3

Comments

Comment from Michael Taktikos, Sep 04 2004: The following is a much simpler definition of this sequence: a[1] = 1; a[n_] := Mod[Sum[a[k], {k, 1, n - 1}], n - 1]

Links

Table of n, a(n) for n=1..30.

Formula

a(n+1) = sum{k=1 to n} (sum{j|k} a(j)) * p(n-k), where p(k) is the number of partitions of k (A000041).

Example

We have the partitions of 4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4; replace and add: 1+1+1+1 +1+1+1 +1+3 +1+1 +8 = 21 = a(5).

Mathematica

a[1] = 1; a[n_] := a[n] = Block[{j, k, s = 0}, For[k = 1, k < n, k++, j = Divisors[k]; s = s + Plus @@ ((a /@ j)PartitionsP[n - k - 1])]; s]; Table[ a[n], {n, 30}] (* Robert G. Wilson v, Aug 25 2004 *) (* or slower *)
(* first *) Needs["DiscreteMath`Combinatorica`"] (* then *) a[1] = 1; a[n_] := a[n] = Block[{p = Sort[ Flatten[ Partitions[n - 1]] ]}, Plus @@ (a /@ p)]; Table[ a[n], {n, 30}] (* Robert G. Wilson v, Aug 25 2004 *)

Crossrefs

Sequence in context: A238831 A322059 A259714 * A007835 A152086 A014396

Adjacent sequences: A096767 A096768 A096769 * A096771 A096772 A096773

Keyword

nonn,easy

Author

Leroy Quet, Aug 17 2004

Extensions

More terms from Robert G. Wilson v, Aug 25 2004

Status

approved