login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000084 Number of series-parallel networks with n unlabeled edges. Also called yoke-chains by Cayley and MacMahon.
(Formerly M1207 N0466)
32
1, 2, 4, 10, 24, 66, 180, 522, 1532, 4624, 14136, 43930, 137908, 437502, 1399068, 4507352, 14611576, 47633486, 156047204, 513477502, 1696305728, 5623993944, 18706733128, 62408176762, 208769240140, 700129713630, 2353386723912 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

This is a series-parallel network: o-o; all other series-parallel networks are obtained by connecting two series-parallel networks in series or in parallel.

Also the number of unlabeled cographs on n nodes. - N. J. A. Sloane and Eric W. Weisstein, Oct 21 2003

Also the number of P_4-free graphs on n nodes. - Gordon F. Royle, Jul 04 2008

Equals row sums of triangle A144962 and the INVERT transform of A001572. - Gary W. Adamson, Sep 27 2008

See Cameron (1987) p. 165 for a bijection between series-parallel networks and cographs. - Michael Somos, Apr 19 2014

REFERENCES

Antoni Amengual, The intriguing properties of the equivalent resistances of n equal resistors combined in series and in parallel, American Journal of Physics, 68(2), 175-179 (February 2000). DOI: http://dx.doi.org/10.1119/1.19396 - _Sameen Ahmed Khan, Mar 06 2010

A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, SIAM Publications, 1999. (For definition of cograph)

Cameron, Peter J. Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155--183. MR0891613 (89a:05009). See p. 155. - N. J. A. Sloane, Apr 18 2014

P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.

S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.

S. A. Khan, How Many Equivalent Resistances?, RESONANCE, May 2012; http://www.ias.ac.in/resonance/May2012/p468-475.pdf. - N. J. A. Sloane, Oct 15 2012

S. A. Khan, Farey sequences and resistor networks, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 122, No. 2, May 2012, pp. 153-162. - N. J. A. Sloane, Oct 23 2012

D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p. 589, Answers to Exercises Section 2.3.4.4 5.

Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.

P. A. MacMahon, Yoke-trains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616. Page 333 gives A000084 = 2*A000669.

P. A. MacMahon, The combination of resistances, The Electrician, 28 (1892), 601-602; reprinted in Coll. Papers I, pp. 617-619. Reprinted in Discrete Appl. Math., 54 (1994), 225-228.

J. W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 142.

J. Riordan and C. E. Shannon, The number of two-terminal series-parallel networks, J. Math. Phys., 21 (1942), 83-93. Reprinted in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 560-570.

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).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.40, notes on p. 133.

Takeaki Uno, Ryuhei Uehara and Shin-ichi Nakano, Bounding the Number of Reduced Trees, Cographs, and Series-Parallel Graphs by Compression,  in WALCOM: ALGORITHMS AND COMPUTATION, Lecture Notes in Computer Science, 2012, Volume 7157/2012, 5-16, DOI: 10.1007/978-3-642-28076-4_4. - N. J. A. Sloane, Jul 07 2012

LINKS

N. J. A. Sloane, Table of n, a(n) for n=1..1001

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

S. R. Finch, Series-parallel networks

O. Golinelli, Asymptotic behavior of two-terminal series-parallel networks.

S. Hougardy, Home Page

ISCGI, Cograph graphs

Sameen Ahmed Khan, Mathematica notebook for A048211 and A000084

Sameen Ahmed Khan, The bounds of the set of equivalent resistances of n equal resistors combined in series and in parallel, arxiv:1004.3346

N. J. A. Sloane, First 1001 terms of A000669 and A000084

Eric Weisstein's World of Mathematics, Cograph

Eric Weisstein's World of Mathematics, Series-Parallel Network

FORMULA

The sequence satisfies Product_{k=1..inf} 1/(1-x^k)^A000669(k) = 1 + Sum_{k=1..inf} a(k)*x^k.

a(n) = 2 * A000669(n) if n>0. - Michael Somos, Apr 17 2014

a(n) ~ C d^n/n^(3/2) where C = 0.412762889201578063700271574144..., d = 3.56083930953894332952612917270966777... is a root of Prod_{ n >= 1} (1-1/x^n)^(-a(n)) = 2. - Riordan, Shannon, Moon, Rains, Sloane

Consider the free algebraic system with two commutative associative operators (x+y) and (x*y) and one generator A. The number of elements with n occurrences of the generator is a(n). - Michael Somos, Oct 11 2006. Examples: n=1: A. n=2: A+A, A*A. n=3: A+A+A, A+(A*A), A*(A+A), A*A*A.

EXAMPLE

G.f. = x + 2*x^2 + 4*x^3 + 10*x^4 + 24*x^5 + 66*x^6 + 180*x^7 + 522*x^8 + ...

The series-parallel networks with 1, 2 and 3 edges are:

1 edge: o-o

2 edges: o-o-o o=o

....................... /\

3 edges: o-o-o-o o-o=o o--o o-o-o

....................... \/ ..\_/

MAPLE

(continue from A000669) A000084 := n-> if n=1 then 1 else 2*A000669(n); fi;

# N denotes all series-parallel networks, S = series networks, P = parallel networks; spec84 := [ N, {N=Union(Z, S, P), S=Set(Union(Z, P), card>=2), P=Set(Union(Z, S), card>=2)} ]: A000084 := n->combstruct[count](spec84, size=n);

MATHEMATICA

m = 27; 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];

eq[0] = Thread[coes == 0] // Rest;

Do[s[k] = Solve[eq[k - 1][[1]], a[k]] // First; eq[k] = eq[k - 1] /. s[k] // Rest, {k, 1, m}];

Array[a, m] /. Flatten @ Table[s[k], {k, 1, m}]

(* Jean-Fran├žois Alcover, Jun 20 2011 *)

PROG

(PARI) {a(n) = local(A); if( n<1, 0, A = 1 / (1 - x + x * O(x^n)); for(k=2, n, A /= (1 - x^k + x * O(x^n))^polcoeff(A, k)); polcoeff(A, n))}; /* Michael Somos, Oct 11 2006 */

CROSSREFS

Cf. A058351, A058352, A058353, A000311, A006351 (labeled version).

See also A058964, A058965.

Cf. A144962, A001572. - Gary W. Adamson, Sep 27 2008

Cf. A176500, A176502. - Sameen Ahmed Khan, Apr 27 2010

Sequence in context: A000682 A001997 A239605 * A057734 A151516 A003104

Adjacent sequences:  A000081 A000082 A000083 * A000085 A000086 A000087

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More decimal places in the third formula added by Vaclav Kotesovec, Jun 24 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 25 02:02 EDT 2014. Contains 248517 sequences.