A116380 Number of quaternary rooted identity (distinct subtrees) trees with n nodes.

1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 247, 548, 1226, 2770, 6298, 14419, 33183, 76760, 178327, 415960, 973693, 2286781, 5386573, 12723097, 30127465, 71506140, 170081575, 405359177, 967899981, 2315131955, 5546597838, 13308818691, 31979667219, 76947325788

Offset: 1

Author

Karen A. Yeats, Feb 06 2006

Keywords

• nonn

Comments

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.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Jason P. Bell, Stanley N. Burris and Karen A. Yeats, Counting Rooted Trees: The Universal Law t(n) ~ C rho^{-n} n^{-3/2}, arXiv:math/0512432 [math.CO], 2005-2006.

Crossrefs

Cf. A004111, A063895, A116379.

Programs

C

#include  using namespace GiNaC; int main(){ int i, order=40; symbol x("x"); ex T; for (i=0; i
				

Maple

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+ T(x)^4/24- T(x)^2* T(x^2)/4+ T(x)* T(x^3)/3+ T(x^2)^2/8- T(x^4)/4), 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

Mathematica

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+T[y]^4/24-T[y]^2*T[y^2]/4+T[y]*T[y^3]/3+T[y^2]^2/8-T[y^4]/4), {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 *)

Formula

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 + A(x)^4/24-A(x)^2A(x^2)/4+A(x)A(x^3)/3+A(x^2)^2/8-A(x^4)/4), that is A(x) = x(1+Set_{<=4}(A)(x)).