login
Number of trees with n nodes and 2-colored internal (non-leaf) nodes.
(Formerly M1422)
17

%I M1422 #29 Dec 26 2021 20:51:19

%S 1,1,1,2,5,12,33,98,305,1002,3424,12016,43230,158516,590621,2230450,

%T 8521967,32889238,128064009,502590642,1986357307,7900377892,

%U 31602819524,127076645038,513419837168,2083414420394,8488377206876,34712566540014,142443837953632

%N Number of trees with n nodes and 2-colored internal (non-leaf) nodes.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A004114/b004114.txt">Table of n, a(n) for n = 0..500</a>

%H F. Harary, R. W. Robinson and A. J. Schwenk, <a href="https://doi.org/10.1017/S1446788700016190">Twenty-step algorithm for determining the asymptotic number of trees of various species</a>, J. Austral. Math. Soc., Series A, 20 (1975), 483-503. <a href="https://doi.org/10.1017/S1446788700033760">Errata</a>: Vol. A 41 (1986), p. 325.

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F G.f.: 1+B(x)-x*B(x)-B(x)^2/2+B(x^2)/2 where B(x) is g.f. of A004113. - _Christian G. Bower_, Dec 15 1999

%F a(n) ~ c * d^n / n^(5/2), where d = 4.49415643203339504537343052... (same as for A004113), c = 0.31497820931312537077... . - _Vaclav Kotesovec_, Sep 12 2014

%t max = 28; etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}]*b[n - j], {j, 1, n}]/n ]; b]; bb = etr[A004113]; A004113[n_] := If[n <= 1, n, 2*bb[n - 1]]; b[x_] := Sum[A004113[n] x^n, {n, 1, max}]; f[x_] := Sum[a[n] x^n, {n, 0, max}]; a[0] = a[1] = a[2] = 1; coes = CoefficientList[ Series[f[x] - (1 + b[x] - x*b[x] - b[x]^2/2 + b[x^2]/2), {x, 0, max}], x]; Table[a[n], {n, 0, max}] /. Solve[Thread[coes == 0]][[1]] (* _Jean-François Alcover_, Jan 29 2013, after _Alois P. Heinz_ *)

%Y Cf. A004113, A052316, A052317.

%K nonn,nice,easy

%O 0,4

%A _N. J. A. Sloane_

%E More terms, and new description from _Christian G. Bower_, Dec 15 1999