login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A104653
Number of topologically distinct trees with n vertices, including Steiner trees.
1
0, 1, 4, 27, 270, 3645, 62370, 1295595, 31689630, 892387125, 28439784450, 1011998000475, 39773696712750, 1711186282730925, 79990996596761250, 4037168079574504875, 218797477268743122750, 12673229445076108033125
OFFSET
1,3
COMMENTS
Let F(n,s) = number of Steiner trees with n vertices and s Steiner points; then A001147 is also F(n,n-2) for n>2. - Robert G. Wilson v, May 10 2005
LINKS
E. N. Gilbert and H. O. Pollak, Steiner minimal trees, SIAM J. Appl. Math. 16, (1968), pp. 1-29.
FORMULA
a(n) = Sum_{s=0..n-2} 2^(-s)*binomial(n, s+2)*(n+s-2)!/s!. - Robert G. Wilson v, May 10 2005
a(n) ~ 3^(3/4) * (2 + sqrt(3))^(n - 3/2) * n^(n-2) / exp(n). - Vaclav Kotesovec, Nov 27 2017
EXAMPLE
Let F(n,s) = number of Steiner trees with n vertices and s Steiner points. Then a(3)=4 because we can have F(3,0)=3 and F(3,1)=1.
MATHEMATICA
f[n_] := Sum[ Binomial[n, k + 2](n + k - 2)!/(k!2^k), {k, 0, n - 2}]; Table[ f[n], {n, 18}] (* Robert G. Wilson v, May 10 2005 *)
CROSSREFS
Cf. A001147.
Sequence in context: A265270 A161633 A052871 * A194787 A020558 A259485
KEYWORD
easy,nonn
AUTHOR
Alexandre Goncalves (alexg(AT)civil.ist.utl.pt), Apr 22 2005
EXTENSIONS
More terms from Robert G. Wilson v, May 10 2005
STATUS
approved