cp's OEIS Frontend

A002988 Number of trimmed trees with n nodes.

%I A002988 M0777 #41 Jan 31 2022 06:47:19
%S A002988 1,1,1,0,1,1,2,3,6,10,21,39,82,167,360,766,1692,3726,8370,18866,43029,
%T A002988 98581,227678,528196,1232541,2888142,6798293,16061348,38086682,
%U A002988 90607902,216230205,517482053,1241778985,2987268628,7203242490
%N A002988 Number of trimmed trees with n nodes.
%C A002988 From _Christian G. Bower_, Dec 15 1999: (Start)
%C A002988 A trimmed tree is a tree with a forbidden limb of length 2.
%C A002988 A tree with a forbidden limb of length k is a tree where the path from any leaf inward hits a branching node or another leaf within k steps. (End)
%D A002988 K. L. McAvaney, personal communication.
%D A002988 A. J. Schwenk, Almost all trees are cospectral, pp. 275-307 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
%D A002988 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002988 Alois P. Heinz, <a href="/A002988/b002988.txt">Table of n, a(n) for n = 0..1000</a>
%H A002988 R. K. Guy and J. L. Selfridge, <a href="http://www.jstor.org/stable/2319392">The nesting and roosting habits of the laddered parenthesis</a>, Amer. Math. Monthly 80 (8) (1973), 868-876.
%H A002988 R. K. Guy and J. L. Selfridge, <a href="/A003018/a003018.pdf">The nesting and roosting habits of the laddered parenthesis</a> (annotated cached copy)
%H A002988 A. J. Schwenk, <a href="/A002988/a002988.pdf">Letter to N. J. A. Sloane, Aug 1972</a>
%H A002988 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A002988 G.f.: 1 + B(x) + (B(x^2) - B(x)^2)/2 where B(x) is the g.f. of A002955. - _Christian G. Bower_, Dec 15 1999
%F A002988 a(n) ~ c * d^n / n^(5/2), where d = 2.59952511060090659632378883695..., c = 0.3758284247032014502508501798... . - _Vaclav Kotesovec_, Aug 24 2014
%p A002988 with(numtheory):
%p A002988 g:= proc(n) g(n):= `if`(n=0, 1, add(add(d*(g(d-1)-
%p A002988       `if`(d=2, 1, 0)), d=divisors(j))*g(n-j), j=1..n)/n)
%p A002988     end:
%p A002988 a:= n-> `if`(n=0, 1, g(n-1)+(`if`(irem(n, 2, 'r')=0,
%p A002988          g(r-1), 0)-add(g(i-1)*g(n-i-1), i=1..n-1))/2):
%p A002988 seq(a(n), n=0..40);  # _Alois P. Heinz_, Jul 06 2014
%t A002988 g[n_] := g[n] = If[n == 0, 1, Sum[Sum[d*(g[d-1]-If[d == 2, 1, 0]), {d, Divisors[j] }]*g[n-j], {j, 1, n}]/n]; a[n_] := If[n == 0, 1, g[n-1] + (If[Mod[n, 2] == 0, g[Quotient[n, 2]-1], 0] - Sum[g[i-1]*g[n-i-1], {i, 1, n-1}])/2]; Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Feb 25 2015, after _Alois P. Heinz_ *)
%Y A002988 Cf. A002955, A002989-A002992, A052318-A052329.
%K A002988 nonn,nice
%O A002988 0,7
%A A002988 _N. J. A. Sloane_
%E A002988 More terms from _Christian G. Bower_, Dec 15 1999