A001677 Number of series-parallel networks with n edges.

1, 2, 3, 6, 12, 26, 59, 146, 368, 976, 2667, 7482, 21440, 62622, 185637, 557680, 1694256, 5198142, 16086486, 50165218, 157510504, 497607008, 1580800091, 5047337994, 16190223624, 52153429218, 168657986843, 547389492416

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Examples

			a(5) = 24 - (1/2)*(1*10+2*4+4*2+10*1) = 6.
		

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).
• B. D. H. Tellegen, Geometrical configurations and duality of electrical networks, Philips Technical Review, 5 (1940), 324-330.

Links

• T. D. Noe, Table of n, a(n) for n=2..500
• R. M. Foster, The number of series-parallel networks, Proc. Intern. Congr. Math., Vol. 1, 1950, p. 646.

Crossrefs

Cf. A058642, A058668.

Programs

Mathematica

m = 29; ClearAll[a, b, s]; a[1] = 1; a[2] = 2; a[3] = 4; b[1] = 1; b[n_ /; n >= 2] = a[n]/2; ex = Product[ 1/(1-x^k)^b[k], {k, 1, m}] - 1 - Sum[ a[k]*x^k, {k, 1, m}]; coes = CoefficientList[ Series[ ex, {x, 0, m}], x]; sol = Solve[ Thread[ coes == 0]][[1]]; Do[ s[k] = a[k] /. sol, {k, 1, m}]; a[2] = 1; a[3] = 2; a[n_] := s[n] - (1/2)*Sum[ s[i]*s[n-i], {i, 1, n-1}] - If[ OddQ[n], 0, s[n/2]/2]; Table[ a[n], {n, 2, m}] (* Jean-François Alcover, Feb 24 2012 *)

Formula

a(n) = s(n) - (1/2)*Sum_{i=1..n-1} s(i)*s(n-i) - (1/2)*s(n/2), where s() = A000084 and the last term is omitted if n is odd.

Extensions

More terms from David W. Wilson, Sep 20 2000