login
A214579
Number of partitions of n in which each part is divisible by the next and have no parts equal to 1.
1
0, 1, 1, 2, 1, 4, 1, 5, 3, 7, 1, 13, 1, 12, 8, 16, 1, 26, 1, 29, 13, 28, 1, 51, 6, 42, 19, 56, 1, 87, 1, 77, 29, 79, 16, 134, 1, 106, 43, 145, 1, 195, 1, 178, 77, 177, 1, 288, 11, 253, 80, 278, 1, 379, 32, 361, 107, 352, 1, 573, 1, 440, 163, 516, 46, 699, 1, 627, 178, 701, 1, 961, 1, 776, 288, 884, 37
OFFSET
1,4
COMMENTS
Also number of generalized Bethe trees with n+1 vertices having root degree >=2.
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.
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).
O. Rojo, Spectra of weighted generalized Bethe trees joined at the root, Linear Algebra and its Appl., 428, 2008, 2961-2979.
FORMULA
a(n) = A003238(n+1) - A003238(n).
a(n) = b(n) - b(n-1), where b(0)=1 and b(n) = Sum_{j|n} b(j-1) (n>=1).
EXAMPLE
a(6) = 4 because we have 6, 42, 33, and 222.
a(8) = 5 because we have 8, 62, 44, 422, and 2222.
MAPLE
with(numtheory): b := proc (n) if n = 0 then 1 else add(b(divisors(n)[i]-1), i = 1 .. tau(n)) end if end proc: a := proc (n) options operator, arrow: b(n)-b(n-1) end proc: seq(a(n), n = 1 .. 80);
MATHEMATICA
b[1] = 1; b[n_] := b[n] = Total[b /@ Divisors[n-1]];
A214579 = Array[b, 100] // Differences (* Jean-François Alcover, Mar 27 2017, adapted from Maple *)
CROSSREFS
Cf. A003238.
Sequence in context: A277100 A337363 A339243 * A083711 A339619 A018783
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Aug 18 2012
STATUS
approved