cp's OEIS Frontend

A300442 Number of binary strict trees of weight n.

%I A300442 #28 May 14 2021 08:09:10
%S A300442 1,1,1,2,3,6,10,23,46,108,231,561,1285,3139,7348,18265,43907,109887,
%T A300442 267582,675866,1669909,4238462,10555192,26955062,67706032,173591181,
%U A300442 438555624,1129088048,2869732770,7410059898,18911818801,48986728672,125562853003,326011708368
%N A300442 Number of binary strict trees of weight n.
%C A300442 A binary strict tree of weight n > 0 is either a single node of weight n, or an ordered pair of binary strict trees with strictly decreasing weights summing to n.
%H A300442 Alois P. Heinz, <a href="/A300442/b300442.txt">Table of n, a(n) for n = 0..1000</a>
%F A300442 a(n) = 1 + Sum_{x + y = n, 0 < x < y < n} a(x) * a(y).
%e A300442 The a(5) = 6 binary strict trees: 5, (41), (32), ((31)1), ((21)2), (((21)1)1).
%e A300442 The a(6) = 10 binary strict trees:
%e A300442   6,
%e A300442   (51), (42),
%e A300442   ((41)1), ((32)1), ((31)2),
%e A300442   (((31)1)1), (((21)2)1), (((21)1)2),
%e A300442   ((((21)1)1)1).
%p A300442 a:= proc(n) option remember;
%p A300442       1+add(a(j)*a(n-j), j=1..(n-1)/2)
%p A300442     end:
%p A300442 seq(a(n), n=0..40);  # _Alois P. Heinz_, Mar 06 2018
%t A300442 k[n_]:=k[n]=1+Sum[Times@@k/@y,{y,Select[IntegerPartitions[n],Length[#]===2&&UnsameQ@@#&]}];
%t A300442 Array[k,40]
%t A300442 (* Second program: *)
%t A300442 a[n_] := a[n] = 1 + Sum[a[j]*a[n - j], {j, 1, (n - 1)/2}];
%t A300442 a /@ Range[0, 40] (* _Jean-François Alcover_, May 13 2021, after _Alois P. Heinz_ *)
%o A300442 (PARI) seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sum(k=1, (n-1)\2, v[k]*v[n-k])); concat([1], v)} \\ _Andrew Howroyd_, Aug 25 2018
%Y A300442 Cf. A000992, A001190, A063834, A196545, A273873, A289501, A292432, A293511, A300352, A300440, A300443.
%K A300442 nonn
%O A300442 0,4
%A A300442 _Gus Wiseman_, Mar 05 2018