cp's OEIS Frontend

A273873 Number of strict trees of weight n.

%I A273873 #29 May 09 2021 07:56:48
%S A273873 1,1,2,3,6,12,28,65,166,412,1076,2806,7524,20020,54744,148417,410078,
%T A273873 1126732,3144500,8728570,24555900,68713420,194469616,548088278,
%U A273873 1559301428,4418131108,12628267512,35957541462,103150588492,294924202032,848878072440,2435729999665
%N A273873 Number of strict trees of weight n.
%C A273873 A strict tree t is either (case 1) a positive integer t = n, or (case 2) a set t = {t1, t2, ..., tk} of two or more strict trees (i.e. branches) with distinct weights, where the weight of a strict tree in the second case is the sum of the weights of its branches; hence the multiset of weights is a strict integer partition of n. For example, {{{{{2,1},1},2},3},{4,{2,1}},{2,1},1} is a strict tree of weight 20.
%H A273873 Alois P. Heinz, <a href="/A273873/b273873.txt">Table of n, a(n) for n = 1..2000</a>
%H A273873 H. Gingold and A. Knopfmacher, <a href="http://dx.doi.org/10.4153/CJM-1995-062-9">Analytic properties of power product expansions</a>, Canad. J. Math. 47(1995), 1219-1239
%H A273873 Gus Wiseman, <a href="https://docs.google.com/document/d/1m0s6DGTBkDW9gvMuFmJHvy6oLGRAbQ7okAZcOPZawp0/pub">Comcategories and Multiorders</a>, <a href="http://www.nafindix.com/math/academic/ComcategoriesandMultiordersv7.pdf">(pdf version)</a>
%H A273873 Gus Wiseman, <a href="/A273873/a273873.png">All strict trees n=1..6.</a>
%F A273873 Sum_{g(t)=y} (-1)^{d(t)} = mu(|y|<={y_1,...,y_k}), where mu is the Mobius function of the multiorder of integer partitions, g(t) is the multiset of leaves of a strict tree t, and d(t) is the number of branchings.
%F A273873 Strict trees are closely related to the coefficients appearing in a(i) = Sum_y c(y_1)*...*c(y_k) where Sum_i c(i)*x^i = Prod_i (1 + a(i)*x^i). The latter identity is the formal power product expansion (PPE) of an (ordinary) generating function.
%e A273873 a(6) = 12: {6, (51), (42), ((41)1), (321), ((31)2), ((32)1), (((31)1)1), ((21)21), (((21)1)2), (((21)2)1), ((((21)1)1)1)}.
%p A273873 b:= proc(n, i) option remember; `if`(i*(i+1)/2<n, 0,
%p A273873      `if`(n=0, 1, b(n, i-1)+b(n-i, min(n-i, i-1))*a(i)))
%p A273873     end:
%p A273873 a:= n-> 1+b(n, n-1):
%p A273873 seq(a(n), n=1..35);  # _Alois P. Heinz_, Jun 02 2016
%t A273873 STE[n_Integer?Positive]:=STE[n]=1+Plus@@Map[Function[ptn,Times@@STE/@ptn],Select[IntegerPartitions[n],And[Length[#]>1,UnsameQ@@#]&]];
%t A273873 Array[STE,30]
%t A273873 (* Second program: *)
%t A273873 b[n_, i_] := b[n, i] = If[i(i + 1)/2 < n, 0,
%t A273873      If[n == 0, 1, b[n, i - 1] + b[n - i, Min[n - i, i - 1]] a[i]]];
%t A273873 a[n_] := If[n == 0, 1, 1 + b[n, n - 1]];
%t A273873 a /@ Range[35] (* _Jean-François Alcover_, May 09 2021, after _Alois P. Heinz_ *)
%o A273873 (PARI) seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + polcoef(prod(k=1, n-1, 1 + v[k]*x^k + O(x*x^n)), n)); v} \\ _Andrew Howroyd_, Aug 26 2018
%Y A273873 Cf. A196545 (weakly ordered plane trees); A220418, A220420 (power product expansions); A271619, A063834 (twice partitioned numbers), A289501.
%K A273873 nonn
%O A273873 1,3
%A A273873 _Gus Wiseman_, Jun 01 2016