|
|
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).
|
|
5
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,8
|
|
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).
|
|
LINKS
|
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).
|
|
FORMULA
|
T(n,1)=1; T(n,k) = Sum_{j|k}T(n-k,j); T(n,k)=0 if k>n.
|
|
EXAMPLE
|
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;
|
|
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|