cp's OEIS Frontend

A116379 Number of ternary rooted identity (distinct subtrees) trees with n nodes.

%I A116379 #24 Feb 21 2020 15:01:20
%S A116379 1,1,1,2,3,6,12,25,52,113,245,542,1205,2707,6113,13907,31780,73010,
%T A116379 168399,389991,906231,2112742,4939689,11580640,27216387,64110091,
%U A116379 151334814,357938832,848153045,2013190671,4786210412,11396004660,27172368314,64875527649
%N A116379 Number of ternary rooted identity (distinct subtrees) trees with n nodes.
%C A116379 It is not known if these trees have the asymptotic form C rho^{-n} n^{-3/2}, whereas the identity binary trees, A063895, do, see the Jason P. Bell et al. reference.
%H A116379 Alois P. Heinz, <a href="/A116379/b116379.txt">Table of n, a(n) for n = 1..1000</a>
%H A116379 Jason P. Bell, Stanley N. Burris and Karen A. Yeats, <a href="https://arxiv.org/abs/math/0512432">Counting Rooted Trees: The Universal Law t(n) ~ C rho^{-n} n^{-3/2}</a>, arXiv:math/0512432 [math.CO], 2005-2006.
%F A116379 G.f. satisfies: A(x) = x(1+A(x)+A(x)^2/2-A(x^2)/2+A(x)^3/6-A(x)A(x^2)/2+A(x^3)/3), that is A(x) = x(1+Set_{<=3}(A)(x)).
%p A116379 A:= proc(n) option remember; local T; if n<=1 then x else T:= unapply(A(n-1), x); convert(series(x* (1+T(x)+ T(x)^2/2- T(x^2)/2+ T(x)^3/6- T(x)*T(x^2)/2+ T(x^3)/3), x, n+1), polynom) fi end: a:= n-> coeff(A(n), x, n): seq(a(n), n=1..40);  # _Alois P. Heinz_, Aug 22 2008
%t A116379 A[n_] := A[n] = If[n <= 1, x, T[y_] = A[n-1] /. x -> y; Normal[Series[y*(1+T[y]+T[y]^2/2-T[y^2]/2+T[y]^3/6-T[y]*T[y^2]/2+T[y^3]/3), {y, 0, n+1}]] /. y -> x] ; a[n_] := Coefficient[A[n], x, n]; Table[a[n], {n, 1, 40}] (* _Jean-François Alcover_, Feb 13 2014, after Maple *)
%o A116379 (C) #include <ginac/ginac.h> using namespace GiNaC; int main(){ int i, order = 40; symbol x("x"); ex T = x; for (i=0; i<order; i++) T = (x+x*(T + pow(T,2)/2 - T.subs(x==pow(x,2))/2 + pow(T,3)/6 - T*T.subs(x==pow(x,2))/2 + T.subs(x==pow(x,3))/3)).series(x, i+2); for (i=1; i<=order; i++) std::cout << T.coeff(x, i) << ", "; }
%Y A116379 Cf. A004111, A063895, A116380.
%K A116379 nonn
%O A116379 1,4
%A A116379 _Karen A. Yeats_, Feb 06 2006