A214579 Number of partitions of n in which each part is divisible by the next and have no parts equal to 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

Alois P. Heinz, Table of n, a(n) for n = 1..10000

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

Adjacent sequences: A214576 A214577 A214578 * A214580 A214581 A214582

Keyword

nonn

Author

Emeric Deutsch, Aug 18 2012

Status

approved