login
Number of Steiner topologies on n points.
2

%I #25 Dec 07 2021 03:24:51

%S 1,4,31,360,5625,110880,2643795,74035080,2382538725,86656878000,

%T 3515761193175,157425426358200,7711961781949425,410298436511964000,

%U 23559634669682986875,1452240056377167057000,95649328231839993736125

%N Number of Steiner topologies on n points.

%D F. K. Hwang, D. S. Richards and P. Winter, The Steiner Tree Problem, North-Holland, 1992, see p. 14.

%H Vincenzo Librandi, <a href="/A086677/b086677.txt">Table of n, a(n) for n = 2..100</a>

%F Let f(n) = (2*n-4)!/(2^(n-2)*(n-2)!) (A001147) and let F(n, k) = binomial(n, k+2) f(k) (n+k-2)! / (2k)!. Then a(n) = Sum_{k=0..n-2} Sum_{i=0..floor((n-k-2)/2)} binomial(n, i) F(n-i, k+i) (k+i)! / k!.

%F E.g.f. (for offset 0): 4*(x-3)/(x+1)^4 - (-13+22*x+3*x^2)/((-x^2-4*x+1)^(1/2)*(x+1)^4). - _Mark van Hoeij_, Oct 31 2011

%F a(n) ~ 1/8*sqrt(250-110*sqrt(5)) * n^(n-2) * (2+sqrt(5))^n / exp(n). - _Vaclav Kotesovec_, Mar 10 2014

%F Equivalently, a(n) ~ 5^(3/4) * phi^(3*n - 5/2) * n^(n-2) / (4 * exp(n)), where phi = A001622 is the golden ratio. - _Vaclav Kotesovec_, Dec 07 2021

%t a[n_] := Sum[ Binomial[n, i]*Binomial[n-i, i+k+2]*(n+k-2)!*(2i+2k-1)!!*(i+k)! / ((2*(i+k))!*k!), {k, 0, n-2}, {i, 0, (n-k-2)/2}]; Table[a[n], {n, 2, 18}] (* _Jean-François Alcover_, Sep 03 2012, after formula *)

%Y Cf. A001147.

%K nonn,easy,nice

%O 2,2

%A _N. J. A. Sloane_, Jul 28 2003

%E More terms from _Vladeta Jovovic_, Jul 29 2003