A214575 - OEIS

%I #18 Jan 29 2022 09:11:43

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

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

%U 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

%N 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).

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

%C 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.

%C 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.

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

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

%H Seiichi Manyama, <a href="/A214575/b214575.txt">Rows n = 1..50, flattened</a>

%H M. K. Goldberg and E. M. Livshits, <a href="http://mi.mathnet.ru/eng/mz9458">On minimal universal trees</a>, Mathematical Notes of the Acad. of Sciences of the USSR, 4, 1968, 713-717 (translation from the Russian Mat. Zametki 4 1968 371-379).

%H O. Rojo, <a href="http://dx.doi.org/10.1016/j.laa.2008.01.026">Spectra of weighted generalized Bethe trees joined at the root</a>, Linear Algebra and its Appl., 428, 2008, 2961-2979.

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

%e T(7,4)=2 because we have (4,2,1) and (4,1,1,1).

%e Triangle starts:

%e   1;

%e   1, 1;

%e   1, 1, 1;

%e   1, 2, 1, 1;

%e   1, 2, 1, 1, 1;

%e   1, 3, 2, 2, 1, 1;

%p 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

%Y An augmented version is A301343.

%Y Cf. A122934, A214576.

%K nonn,tabl

%O 1,8

%A _Emeric Deutsch_, Aug 18 2012