A000147 Number of trees of diameter 5.

0, 0, 0, 0, 0, 1, 2, 7, 14, 32, 58, 110, 187, 322, 519, 839, 1302, 2015, 3032, 4542, 6668, 9738, 14006, 20036, 28324, 39830, 55473, 76875, 105692, 144629, 196585, 266038, 357952, 479664, 639519, 849425, 1123191, 1479972, 1942284, 2540674, 3311415

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

A tree of diameter 5 is formed from two rooted trees of height 2, with their roots joined. - Franklin T. Adams-Watters, Jan 13 2006

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• 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 = 1..1000
• J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
• Index entries for sequences related to trees

Crossrefs

Cf. A034853, A000251 (diameter 6).

Programs

Maple

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
     add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
g:= n-> b((n-1)$2, 2) -b((n-1)$2, 1):
a:= n-> (add(g(i)*g(n-i), i=0..n)+`if`(n::even, g(n/2), 0))/2:
seq(a(n), n=1..45);  # Alois P. Heinz, Feb 09 2016

Mathematica

b[n_, i_, k_] := b[n, i, k] = If[n==0, 1, If[i<1 || k<1, 0, Sum[Binomial[ b[i-1, i-1, k-1]+j-1, j]*b[n-i*j, i-1, k], {j, 0, n/i}]]]; g[n_] := b[n-1, n-1, 2] - b[n-1, n-1, 1]; a[n_] := (Sum[g[i]*g[n-i], {i, 0, n}] + If[EvenQ[n], g[n/2], 0])/2; Table[a[n], {n, 1, 45}] (* Jean-François Alcover, Feb 17 2016, after Alois P. Heinz *)

Formula

If n odd, a(n) = Sum_{k=1..(n-1)/2} b(k)*b(n-k); if n even, a(n) = (Sum_{k=1..n/2-1} b(k)*b(n-k)) + C(b(n/2)+1, 2), where b(n) = P(n-1)-1 = A000065(n-1). - Franklin T. Adams-Watters, Jan 13 2006

Extensions

More terms from Franklin T. Adams-Watters, Jan 13 2006