login
Number of rooted trees with n nodes and 2-colored non-leaf nodes.
(Formerly M1629)
5

%I M1629 #38 Dec 26 2021 20:50:55

%S 1,2,6,18,60,204,734,2694,10162,38982,151920,599244,2389028,9608668,

%T 38945230,158904230,652178206,2690598570,11151718166,46412717826,

%U 193891596436,812748036380,3417407089470,14410094628558,60920843101858,258169745573158,1096494947168142

%N Number of rooted trees with n nodes and 2-colored 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="/A004113/b004113.txt">Table of n, a(n) for n = 1..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 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

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

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

%F Shifts left and halves under EULER transform.

%F a(n) ~ c * d^n / n^(3/2), where d = 4.49415643203339504537343052838796824... and c = 0.368722987377516657464802259... - _Vaclav Kotesovec_, Feb 28 2014

%p with(numtheory): etr:= proc(p) local b; b:= proc(n) option remember; `if`(n=0, 1, (add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n))/n) end end: b:= etr(a): a:= n-> `if`(n<=1, n, 2*b(n-1)): seq(a(n), n=1..30); # _Alois P. Heinz_, Sep 06 2008

%t 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]; b = etr[a]; a[n_] := If[n <= 1, n, 2*b[n - 1]]; Table[a[n], {n, 1, 27}] (* _Jean-François Alcover_, Jan 29 2013, translated from _Alois P. Heinz_'s Maple program *)

%Y Cf. A004114, A052316, A052317.

%K nonn,eigen

%O 1,2

%A _N. J. A. Sloane_

%E Extended with better description from _Christian G. Bower_, Apr 15 1998