A116380 -id:A116380 - cp's OEIS frontend

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

1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 245, 542, 1205, 2707, 6113, 13907, 31780, 73010, 168399, 389991, 906231, 2112742, 4939689, 11580640, 27216387, 64110091, 151334814, 357938832, 848153045, 2013190671, 4786210412, 11396004660, 27172368314, 64875527649

Offset: 1

Karen A. Yeats, Feb 06 2006

nonn

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.

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.

Cf. A004111, A063895, A116380.

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

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

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 *)

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)).

A245749 Number of identity trees with n nodes where the maximal outdegree (branching factor) equals 4.

Original entry on oeis.org

2, 6, 21, 63, 185, 512, 1403, 3750, 9928, 25969, 67462, 174039, 446884, 1142457, 2911078, 7396049, 18746761, 47420345, 119746936, 301941284, 760387426, 1912814031, 4807298905, 12071798139, 30292240853, 75965728619, 190398931985, 476980247827, 1194401725174

Offset: 11

Joerg Arndt and Alois P. Heinz, Jul 31 2014

nonn

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

Column k=4 of A244523.

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b(i-1$2, k$2), j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> b(n-1$2, 4$2) -b(n-1$2, 3$2):
seq(a(n), n=11..60);

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i<1, 0, Sum[Binomial[ b[i-1, i-1, k, k], j]*b[n - i*j, i-1, t - j, k], {j, 0, Min[t, n/i]}]]];
a[n_] :=  b[n-1, n-1, 4, 4] - b[n-1, n-1, 3, 3];
Table[a[n], {n, 11, 60}] (* Jean-François Alcover, Aug 28 2021, after Maple code *)

a(n) = A116380(n) - A116379(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Maple

Mathematica

Formula