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

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, 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, 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

Offset: 0

Author

Zak Seidov, Franklin T. Adams-Watters and Vladeta Jovovic, Sep 21 2006

Keywords

• nonn
• look

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000

Crossrefs

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

Programs

Maple

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
# second Maple program:
with(numtheory):
b:= proc(n) option remember;
      `if`(n=0, 1, add(b((n-d)/d), d=divisors(n) minus{1}))
    end:
a:= n-> `if`(n=0, 1, b(n)+b(n-1));
seq(a(n), n=0..200);  # Alois P. Heinz, Mar 28 2011

Mathematica

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

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 */

Formula

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

Extensions

More terms from R. J. Mathar, May 22 2009

a(0)=1 prepended by Max Alekseyev, Nov 13 2009