A214575 Triangle read by rows: T(n,k) is the number of partitions of n in which each part is divisible by the next and have first part equal to k (1 <= k <= n).

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

Offset: 1

Author

Emeric Deutsch, Aug 18 2012

Keywords

• nonn
• tabl

Comments

T(n,k) is also the number of generalized Bethe trees with n edges and k leaves.

A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree; they are called uniform trees in the Goldberg and Livshits reference.

There is a simple bijection between generalized Bethe trees with n edges and partitions of n in which each part is divisible by the next (the parts are given by the number of edges at the successive levels). We have the correspondences: number of edges --- sum of parts; root degree --- last part; number of leaves --- first part; height --- number of parts.

Sum of entries in row n is A003238(n+1).

Apparently, Sum(k*T(n,k), k>=1) = A038046(n+1).

Examples

			T(7,4)=2 because we have (4,2,1) and (4,1,1,1).
Triangle starts:
  1;
  1, 1;
  1, 1, 1;
  1, 2, 1, 1;
  1, 2, 1, 1, 1;
  1, 3, 2, 2, 1, 1;
		

Links

• Seiichi Manyama, Rows n = 1..50, flattened
• M. K. Goldberg and E. M. Livshits, On minimal universal trees, Mathematical Notes of the Acad. of Sciences of the USSR, 4, 1968, 713-717 (translation from the Russian Mat. Zametki 4 1968 371-379).
• O. Rojo, Spectra of weighted generalized Bethe trees joined at the root, Linear Algebra and its Appl., 428, 2008, 2961-2979.

Crossrefs

An augmented version is A301343.

Cf. A122934, A214576.

Programs

Maple

with(numtheory): T := proc (n, k) if k = 1 then 1 elif n < k then 0 else add(T(n-k, divisors(k)[j]), j = 1 .. tau(k)) end if end proc: for n to 18 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form

Formula

T(n,1)=1; T(n,k) = Sum_{j|k}T(n-k,j); T(n,k)=0 if k>n.