A122934 Triangle T(n,k) = number of partitions of n into k parts, with each part size divisible by the next.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 2, 1, 1, 1, 1, 3, 2, 2, 1, 1, 1, 3, 2, 4, 2, 2, 1, 1, 1, 2, 4, 2, 4, 2, 2, 1, 1, 1, 3, 4, 5, 3, 4, 2, 2, 1, 1, 1, 1, 3, 4, 5, 3, 4, 2, 2, 1, 1, 1, 5, 4, 6, 5, 6, 3, 4, 2, 2, 1, 1, 1, 1, 5, 4, 6, 5, 6, 3, 4, 2, 2, 1, 1, 1, 3, 4, 7, 6, 7, 6, 6, 3, 4, 2, 2, 1, 1

Offset: 1

Author

Franklin T. Adams-Watters, Sep 20 2006

Keywords

• easy
• nonn
• tabl

Examples

			Triangle starts:
  1;
  1, 1;
  1, 1, 1;
  1, 2, 1, 1;
  1, 1, 2, 1, 1;
  1, 3, 2, 2, 1, 1;
  ...
T(6,3) = 2 because of the 3 partitions of 6 into 3 parts, [4,1,1] and [2,2,2] meet the definition; [3,2,1] fails because 2 does not divide 3.
		

Links

• Seiichi Manyama, Rows n = 1..140, flattened (Rows n = 1..50 from G. C. Greubel)
• M. Benoumhani and M. Kolli, Finite topologies and partitions, JIS 13 (2010) # 10.3.5.

Crossrefs

Column k=1..4 give A057427, A032741, A049822, A121895.

Row sums give A003238.

Programs

Mathematica

T[, 1] = 1; T[n, k_] := T[n, k] = DivisorSum[n, If[#==1, 0, T[#-1, k-1]]& ]; Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 30 2016 *)

Formula

T(n,1) = 1. T(n,k+1) = Sum_{d|n, d1} T(d-1,k).