|
Search: id:A104653
|
|
|
| A104653 |
|
Number of topologically distinct trees with n vertices, including Steiner trees. |
|
+0
1
|
|
| 0, 1, 4, 27, 270, 3645, 62370, 1295595, 31689630, 892387125, 28439784450, 1011998000475, 39773696712750, 1711186282730925, 79990996596761250, 4037168079574504875, 218797477268743122750, 12673229445076108033125
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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 (rgwv(AT)rgwv.com), May 10 2005
|
|
REFERENCES
|
Gilbert, E. N., and Pollak, H. O. (1968) Steiner minimal trees. SIAM Journal of Applied Mathematics, 16: 1-29.
|
|
FORMULA
|
a(1) = 0 a(2) = 1 a(n) = sum indexed on s(0 to n-2; 2^s * binomial(n, s+2) * (n+s-2)!/s!
a(1) = 0, a(2) = 1; a(n) = sum_{s=0..n-2} (2^-s)* binomial(n, s+2)*(n+s-2)!/s!. - Robert G. Wilson v (rgwv(AT)rgwv.com), May 10 2005
|
|
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}] (from Robert G. Wilson v (rgwv(AT)rgwv.com), May 10 2005)
|
|
CROSSREFS
|
Cf. A001147.
Sequence in context: A052813 A121353 A052871 this_sequence A020558 A119820 A058155
Adjacent sequences: A104650 A104651 A104652 this_sequence A104654 A104655 A104656
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Alexandre Goncalves (alexg(AT)civil.ist.utl.pt), Apr 22 2005
|
|
EXTENSIONS
|
More terms from Robert G. Wilson v (rgwv(AT)rgwv.com), May 10 2005
|
|
|
Search completed in 0.002 seconds
|
