A096770 - OEIS

%I #10 Mar 29 2015 18:42:42

%S 1,1,3,8,21,51,127,303,734,1751,4200,10004,23918,56981,135958,323996,

%T 772530,1840993,4388456,10458354,24926754,59405383,141581236,

%U 337417607,804153140,1916469872,4567399008,10885108498,25941679513,61824709789

%N 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).

%C 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]

%F 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).

%e 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).

%t 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 *)

%t (* 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 *)

%K nonn,easy

%O 1,3

%A _Leroy Quet_, Aug 17 2004

%E More terms from _Robert G. Wilson v_, Aug 25 2004