

A000084


Number of seriesparallel networks with n unlabeled edges. Also called yokechains by Cayley and MacMahon.
(Formerly M1207 N0466)


35



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 seriesparallel network: oo; all other seriesparallel networks are obtained by connecting two seriesparallel 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_4free 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 seriesparallel networks and cographs.  Michael Somos, Apr 19 2014


REFERENCES

D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p. 589, Answers to Exercises Section 2.3.4.4 5.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 142.
J. Riordan and C. E. Shannon, The number of twoterminal seriesparallel networks, J. Math. Phys., 21 (1942), 8393. Reprinted in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 560570.
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.


LINKS

N. J. A. Sloane, Table of n, a(n) for n=1..1001
Moussa Abdenbi, Alexandre Blondin Massé, Alain Goupil, On the maximal number of leaves in induced subtrees of seriesparallel graphs, Semantic Sensor Networks Workshop 2018, CEUR Workshop Proceedings (2018) Vol. 2113.
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), 175179 (February 2000).  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)
Peter J. Cameron, Some treelike objects Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155183. MR0891613 (89a:05009). See p. 155.  N. J. A. Sloane, Apr 18 2014
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89102.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
S. R. Finch, Seriesparallel networks, July 7, 2003. [Cached copy, with permission of the author]
O. Golinelli, Asymptotic behavior of twoterminal seriesparallel networks, arXiv:condmat/9707023 [condmat.statmech], 1997.
S. Hougardy, Home Page
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 25292571.
ISCGI, Cograph graphs
Yukinao Isokawa, SeriesParallel Circuits and Continued Fractions, Applied Mathematical Sciences, Vol. 10, 2016, no. 27, 1321  1331.
Yukinao Isokawa, Listing up Combinations of Resistances, Bulletin of the Kagoshima University Faculty of Education. Bulletin of the Faculty of Education, Kagoshima University. Natural science, Vol. 67 (2016), pp. 18.
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 [physics.genph], 2010.
S. A. Khan, How Many Equivalent Resistances?, RESONANCE, May 2012.
S. A. Khan, Farey sequences and resistor networks, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 122, No. 2, May 2012, pp. 153162.  From N. J. A. Sloane, Oct 23 2012
Sameen Ahmed Khan, Beginning to count the number of equivalent resistances, Indian Journal of Science and Technology, 2016, Vol 9(44).
Z. A. Lomnicki, Twoterminal seriesparallel networks, Adv. Appl. Prob., 4 (1972), 109150.
P. A. MacMahon, Yoketrains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330346; reprinted in Coll. Papers I, pp. 600616. Page 333 gives A000084 = 2*A000669.
P. A. MacMahon, The combination of resistances, The Electrician, 28 (1892), 601602; reprinted in Coll. Papers I, pp. 617619. Reprinted in Discrete Appl. Math., 54 (1994), 225228.
J. W. Moon, Some enumerative results on seriesparallel networks, Annals Discrete Math., 33 (1987), 199226.
J. Riordan and C. E. Shannon, The number of twoterminal seriesparallel networks (annotated scanned copy)
N. J. A. Sloane, Illustrations of a(1)a(4)
N. J. A. Sloane, First 1001 terms of A000669 and A000084
Marx Stampfli, Bridged graphs, circuits and Fibonacci numbers. Applied Mathematics and Computation. Volume 302, 1 June 2017, Pages 6879.
Takeaki Uno, Ryuhei Uehara and Shinichi Nakano, Bounding the Number of Reduced Trees, Cographs, and SeriesParallel Graphs by Compression, in WALCOM: Algorithms and Computation, Lecture Notes in Computer Science, 2012, Volume 7157/2012, 516, DOI: 10.1007/9783642280764_4.  N. J. A. Sloane, Jul 07 2012
Eric Weisstein's World of Mathematics, Cograph
Eric Weisstein's World of Mathematics, SeriesParallel Network


FORMULA

The sequence satisfies Product_{k>=1} 1/(1x^k)^A000669(k) = 1 + Sum_{k>=1} 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 Product_{n>=1} (11/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 seriesparallel networks with 1, 2 and 3 edges are:
1 edge: oo
2 edges: ooo o=o
....................... /\
3 edges: oooo oo=o oo ooo
....................... \/ ..\_/


MAPLE

# (continue from A000669):
A000084 := n> if n=1 then 1 else 2*A000669(n); fi;
# N denotes all seriesparallel 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

n = 27; s = 1/(1x) + O[x]^(n+1); Do[s = s/(1x^k)^Coefficient[s, x^k] + O[x]^(n+1), {k, 2, n}]; CoefficientList[s, x] // Rest (* JeanFrançois Alcover, Jun 20 2011, updated Jun 30 2015 *)
(* faster method: *)
sequenceA000084[n_] := Module[{product, x}, product[1] = Series[1/(1  x), {x, 0, n}]; product[k_] := product[k] = Series[product[k  1]/(1  x^k)^Coefficient[ product[k  1], x^k], {x, 0, n}]; Quiet[Rest[CoefficientList[product[n], x]]]]; sequenceA000084[27] (* Faris Nasybulin, Apr 29 2015 *)


PROG

(PARI) {a(n) = my(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



