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

Links

Seiichi Manyama, Rows n = 1..140, flattened (Rows n = 1..50 from G. C. Greubel)

M. Benoumhani, M. Kolli, Finite topologies and partitions, JIS 13 (2010) # 10.3.5

Formula

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

Example

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.

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

Crossrefs

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

Row sums give A003238.

Sequence in context: A151683 A133912 A277231 * A072170 A368885 A294932

Adjacent sequences: A122931 A122932 A122933 * A122935 A122936 A122937

Keyword

easy,nonn,tabl

Author

Franklin T. Adams-Watters, Sep 20 2006

Status

approved