A002988 Number of trimmed trees with n nodes.
1, 1, 1, 0, 1, 1, 2, 3, 6, 10, 21, 39, 82, 167, 360, 766, 1692, 3726, 8370, 18866, 43029, 98581, 227678, 528196, 1232541, 2888142, 6798293, 16061348, 38086682, 90607902, 216230205, 517482053, 1241778985, 2987268628, 7203242490
Offset: 0
References
- K. L. McAvaney, personal communication.
- 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.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
- R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.
- R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis (annotated cached copy)
- A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972
- Index entries for sequences related to trees
Programs
-
Maple
with(numtheory): g:= proc(n) g(n):= `if`(n=0, 1, add(add(d*(g(d-1)- `if`(d=2, 1, 0)), d=divisors(j))*g(n-j), j=1..n)/n) end: a:= n-> `if`(n=0, 1, g(n-1)+(`if`(irem(n, 2, 'r')=0, g(r-1), 0)-add(g(i-1)*g(n-i-1), i=1..n-1))/2): seq(a(n), n=0..40); # Alois P. Heinz, Jul 06 2014 -
Mathematica
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 *)
Formula
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
a(n) ~ c * d^n / n^(5/2), where d = 2.59952511060090659632378883695..., c = 0.3758284247032014502508501798... . - Vaclav Kotesovec, Aug 24 2014
Extensions
More terms from Christian G. Bower, Dec 15 1999
Comments