A302916 Number of relatively prime p-trees of weight n.

1, 1, 2, 4, 11, 22, 74, 174, 530, 1302, 4713, 10639, 40877, 101795, 325609, 925733, 3432819, 8078511, 32542036, 82226383, 279096823, 795532677, 3066505569, 7374764180, 28946183035, 79313174765, 275507514909, 772692247626, 3049937788372, 7071057261148

Offset

1,3

Comments

A relatively prime p-tree of weight n is either a single node, or a finite sequence of two or more relatively prime p-trees whose weights are weakly decreasing, relatively prime, and sum to n.

Links

Table of n, a(n) for n=1..30.

Example

The a(4) = 4 relatively prime p-trees are (((oo)o)o), ((ooo)o), ((oo)oo), (oooo). Missing from this list is the p-tree ((oo)(oo)).

Mathematica

a[n_]:=a[n]=If[n===1, 1, Sum[Times@@a/@y, {y, Rest[Select[IntegerPartitions[n], Or[Length[#]===1, GCD@@#===1]&]]}]];
Array[a, 20]

Crossrefs

Cf. A000081, A000837, A003238, A004111, A055277, A093637, A196545, A289501, A290689, A300486, A301462, A301467, A302094, A302915, A302917.

Sequence in context: A004646 A072205 A026531 * A038047 A358082 A061152

Adjacent sequences: A302913 A302914 A302915 * A302917 A302918 A302919

Keyword

nonn

Author

Gus Wiseman, Apr 15 2018

Status

approved