A214576 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 last part equal to k (1<=k<=n).

1, 1, 1, 2, 0, 1, 3, 1, 0, 1, 5, 0, 0, 0, 1, 6, 2, 1, 0, 0, 1, 10, 0, 0, 0, 0, 0, 1, 11, 3, 0, 1, 0, 0, 0, 1, 16, 0, 2, 0, 0, 0, 0, 0, 1, 19, 5, 0, 0, 1, 0, 0, 0, 0, 1, 26, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 27, 6, 3, 2, 0, 1, 0, 0, 0, 0, 0, 1, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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 root degree k.

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: root degree --- last part; number of leaves --- first part; height --- number of parts.

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

Examples

			T(9,3)=2 because we have (6,3) and (3,3,3).
Triangle starts:
   1;
   1, 1;
   2, 0, 1;
   3, 1, 0, 1;
   5, 0, 0, 0, 1;
   6, 2, 1, 0, 0, 1;
  10, 0, 0, 0, 0, 0, 1;
		

Links

• Seiichi Manyama, Rows n = 1..140, 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

Cf. A003238, A122934, A214575.

Programs

Maple

with(numtheory): a := proc (n) if n = 0 then 1 else add(a(divisors(n)[j]-1), j = 1 .. tau(n)) end if end proc: T := proc (n, k) if type(n/k, integer) = true then a(n/k-1) else 0 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,k)=a(n/k -1) if k|n and = 0 otherwise; here a(n) is defined by a(0)=1, a(n) = sum_{j|n}a(j-1). We have a(n) = A003238(n+1) = number of partitions of n in which each part is divisible by the next one.