login
A302916
Number of relatively prime p-trees of weight n.
4
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.
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]
KEYWORD
nonn
AUTHOR
Gus Wiseman, Apr 15 2018
STATUS
approved