A300353 Number of strict trees of weight n with odd leaves.

1, 1, 0, 1, 1, 2, 2, 4, 7, 14, 24, 46, 92, 186, 368, 750, 1529, 3160, 6510, 13590, 28374, 59780, 125732, 266468, 564188, 1202842, 2560106, 5484304, 11732400, 25229068, 54187918, 116938702, 252039411, 545593378, 1179545874, 2560009400, 5550315640, 12075064432

Offset

0,6

Comments

This sequence is initially dominated by A300352 but eventually becomes much greater.

A strict tree of weight n > 0 is either a single node of weight n, or a sequence of two or more strict trees with strictly decreasing weights summing to n.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

Formula

O.g.f: (1 + x/(1-x^2) + Product_{i>0} (1 + a(i)x^i))/2.

a(n) = Sum_{i=1..A000009(n)} A294018(A300351(n,i)).

Example

The a(8) = 7 strict trees with odd leaves: (71), (53), (((51)1)1), (((31)3)1), (((31)1)3), ((31)31), (((((31)1)1)1)1).

Mathematica

d[n_]:=d[n]=If[EvenQ[n], 0, 1]+Sum[Times@@d/@y, {y, Select[IntegerPartitions[n], Length[#]>1&&UnsameQ@@#&]}];
Table[d[n], {n, 40}]

Prog

(PARI) seq(n)={my(v=vector(n)); v[1]=1; for(n=2, n, v[n] = polcoef(x/(1-x^2) + prod(k=1, n-1, 1 + v[k]*x^k + O(x*x^n)), n)); concat([1], v)} \\ Andrew Howroyd, Aug 25 2018

Crossrefs

Cf. A000009, A063834, A078408, A089259, A196545, A279374, A279785, A289501, A294018, A294079, A299203, A300300, A300301, A300351, A300352, A300354, A300355.

Sequence in context: A067953 A109070 A169973 * A049868 A120363 A118988

Adjacent sequences: A300350 A300351 A300352 * A300354 A300355 A300356

Keyword

nonn

Author

Gus Wiseman, Mar 03 2018

Status

approved