A300443 Number of binary enriched p-trees of weight n.

1, 1, 2, 3, 8, 15, 41, 96, 288, 724, 2142, 5838, 17720, 49871, 151846, 440915, 1363821, 4019460, 12460721, 37374098, 116809752, 353904962, 1109745666, 3396806188, 10712261952, 33006706419, 104357272687, 323794643722, 1027723460639, 3204413808420, 10193485256501

Offset

0,3

Comments

A binary enriched p-tree of weight n is either a single node of weight n, or an ordered pair of binary enriched p-trees with weakly decreasing weights summing to n.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

a(n) = 1 + Sum_{x + y = n, 0 < x <= y < n} a(x) * a(y).

Example

The a(4) = 8 binary enriched p-trees: 4, (31), (22), ((21)1), ((11)2), (2(11)), (((11)1)1), ((11)(11)).

Maple

a:= proc(n) option remember;
      1+add(a(j)*a(n-j), j=1..n/2)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 06 2018

Mathematica

j[n_]:=j[n]=1+Sum[Times@@j/@y, {y, Select[IntegerPartitions[n], Length[#]===2&]}];
Array[j, 40]
(* Second program: *)
a[n_] := a[n] = 1 + Sum[a[j]*a[n-j], {j, 1, n/2}];
a /@ Range[0, 40] (* Jean-François Alcover, May 12 2021, after Alois P. Heinz *)

Prog

(PARI) seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sum(k=1, n\2, v[k]*v[n-k])); concat([1], v)} \\ Andrew Howroyd, Aug 26 2018

Crossrefs

Cf. A000992, A001190, A063834, A196545, A273873, A289501, A300354, A300439, A300442.

Sequence in context: A148002 A148003 A148004 * A321231 A156802 A148005

Adjacent sequences: A300440 A300441 A300442 * A300444 A300445 A300446

Keyword

nonn

Author

Gus Wiseman, Mar 05 2018

Status

approved