login
Number of partitions of n into distinct parts, with each part divisible by the next.
44

%I #21 Jul 14 2018 04:43:52

%S 1,1,1,2,2,2,3,3,3,4,4,3,5,5,4,6,6,4,6,6,6,9,7,4,7,8,7,9,9,6,10,10,7,

%T 10,8,8,12,9,7,12,13,8,12,12,9,16,12,5,11,13,13,15,13,9,12,15,14,17,

%U 13,7,14,14,11,21,18,13,21,16,10,14,16,12,15,15,10,21,20,13,20,16,17,25,17,9,19

%N Number of partitions of n into distinct parts, with each part divisible by the next.

%H Alois P. Heinz, <a href="/A122651/b122651.txt">Table of n, a(n) for n = 0..10000</a>

%F For n>0, a(n) = A167865(n) + A167865(n-1).

%e a(9) = 4 : [9], [8,1], [6,3], [6,2,1].

%e a(15) = 6 : [15], [14,1], [12,3], [12,2,1], [10,5], [8,4,2,1].

%p A122651r := proc(n,pmax,dv) option remember ; local a,d ; a := 0 ; for d in dv do if d = n and d <= pmax then a := a+1 ; elif d < pmax and n-d > 0 then a := a+A122651r(n-d,d-1,numtheory[divisors](d) minus {d} ) ; fi; od: a ; end: A122651 := proc(n) local i; A122651r(n,n, convert([seq(i,i=1..n)],set) ) ; end: for n from 1 to 120 do printf("%d,",A122651(n)) ; od: # _R. J. Mathar_, May 22 2009

%p # second Maple program:

%p with(numtheory):

%p b:= proc(n) option remember;

%p `if`(n=0, 1, add(b((n-d)/d), d=divisors(n) minus{1}))

%p end:

%p a:= n-> `if`(n=0, 1, b(n)+b(n-1));

%p seq(a(n), n=0..200); # _Alois P. Heinz_, Mar 28 2011

%t b[0] = 1; b[n_] := b[n] = Sum[b[(n - d)/d], {d, Divisors[n] // Rest}]; a[0] = 1; a[n_] := b[n] + b[n-1]; Table[a[n], {n, 0, 84}] (* _Jean-François Alcover_, Mar 26 2013, after _Alois P. Heinz_ *)

%o (PARI) { a(n,m=0) = local(r=0); if(n==0,return(1)); fordiv(n,d, if(d<=m,next); r+=a((n-d)\d,1); ); r } /* _Max Alekseyev_ */

%Y Cf. A003238, A122934, A167439, A167865, A167866, A184999.

%K nonn,look

%O 0,4

%A _Zak Seidov_, _Franklin T. Adams-Watters_ and _Vladeta Jovovic_, Sep 21 2006

%E More terms from _R. J. Mathar_, May 22 2009

%E a(0)=1 prepended by _Max Alekseyev_, Nov 13 2009