cp's OEIS Frontend

A002991 Number of n-node trees with a forbidden limb of length 5.

%I A002991 M0725 #38 Oct 21 2023 01:07:36
%S A002991 1,1,1,1,2,3,5,10,21,43,97,215,503,1187,2876,7033,17510,43961,111664,
%T A002991 285809,737632,1915993,5008652,13163785,34774873,92282214,245930746,
%U A002991 657931603,1766481135,4758553683,12858286083,34844908142,94681272368
%N A002991 Number of n-node trees with a forbidden limb of length 5.
%C A002991 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. - _Christian G. Bower_, Dec 15 1999
%D A002991 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 A002991 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002991 Alois P. Heinz, <a href="/A002991/b002991.txt">Table of n, a(n) for n = 0..1000</a>
%H A002991 A. J. Schwenk, <a href="/A002988/a002988.pdf">Letter to N. J. A. Sloane, Aug 1972</a>.
%H A002991 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A002991 G.f.: 1 + B(x) + (B(x^2) - B(x)^2)/2 where B(x) is g.f. of A052328. - _Christian G. Bower_, Dec 15 1999
%F A002991 a(n) ~ c * d^n / n^(5/2), where d = 2.9447916575019743775137795109303..., c = 0.521642401804532770865780146005... . - _Vaclav Kotesovec_, Aug 25 2014
%p A002991 with(numtheory):
%p A002991 g:= proc(n) g(n):= `if`(n=0, 1, add(add(d*(g(d-1)-
%p A002991       `if`(d=5, 1, 0)), d=divisors(j))*g(n-j), j=1..n)/n)
%p A002991     end:
%p A002991 a:= n-> `if`(n=0, 1, g(n-1)+(`if`(irem(n, 2, 'r')=0,
%p A002991          g(r-1), 0)-add(g(i-1)*g(n-i-1), i=1..n-1))/2):
%p A002991 seq(a(n), n=0..40);  # _Alois P. Heinz_, Jul 06 2014
%t A002991 g[n_] := g[n] = If[n == 0, 1, Sum[Sum[d*(g[d-1]-If[d == 5, 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 26 2015, after _Alois P. Heinz_ *)
%Y A002991 Cf. A002955, A002988-A002992, A052318-A052329.
%K A002991 nonn
%O A002991 0,5
%A A002991 _N. J. A. Sloane_
%E A002991 More terms from _Christian G. Bower_, Dec 15 1999