|
%I M1207 N0466 #140 Sep 22 2023 16:15:04
%S 1,2,4,10,24,66,180,522,1532,4624,14136,43930,137908,437502,1399068,
%T 4507352,14611576,47633486,156047204,513477502,1696305728,5623993944,
%U 18706733128,62408176762,208769240140,700129713630,2353386723912
%N Number of series-parallel networks with n unlabeled edges. Also called yoke-chains by Cayley and MacMahon.
%C 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.
%C Also the number of unlabeled cographs on n nodes. - _N. J. A. Sloane_ and _Eric W. Weisstein_, Oct 21 2003
%C Also the number of P_4-free graphs on n nodes. - _Gordon F. Royle_, Jul 04 2008
%C Equals row sums of triangle A144962 and the INVERT transform of A001572. - _Gary W. Adamson_, Sep 27 2008
%C See Cameron (1987) p. 165 for a bijection between series-parallel networks and cographs. - _Michael Somos_, Apr 19 2014
%D D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p. 589, Answers to Exercises Section 2.3.4.4 5.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 142.
%D 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.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.40, notes on p. 133.
%H N. J. A. Sloane, <a href="/A000084/b000084.txt">Table of n, a(n) for n=1..1001</a>
%H Moussa Abdenbi, Alexandre Blondin Massé, Alain Goupil, <a href="http://ceur-ws.org/Vol-2113/paper1.pdf">On the maximal number of leaves in induced subtrees of series-parallel graphs</a>, Semantic Sensor Networks Workshop 2018, CEUR Workshop Proceedings (2018) Vol. 2113.
%H Antoni Amengual, <a href="http://dx.doi.org/10.1119/1.19396">The intriguing properties of the equivalent resistances of n equal resistors combined in series and in parallel</a>, American Journal of Physics, 68(2), 175-179 (February 2000). - _Sameen Ahmed Khan_, Mar 06 2010
%H A. Brandstaedt, V. B. Le and J. P. Spinrad, <a href="http://dx.doi.org/10.1137/1.9780898719796">Graph Classes: A Survey</a>, SIAM Publications, 1999. (For definition of cograph)
%H Peter J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a> 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
%H P. J. Cameron, <a href="http://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H S. R. Finch, <a href="/A000084/a000084_2.pdf">Series-parallel networks</a>, July 7, 2003. [Cached copy, with permission of the author]
%H Steven R. Finch, <a href="https://doi.org/10.1017/9781316997741">Mathematical Constants II</a>, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
%H O. Golinelli, <a href="http://arXiv.org/abs/cond-mat/9707023">Asymptotic behavior of two-terminal series-parallel networks</a>, arXiv:cond-mat/9707023 [cond-mat.stat-mech], 1997.
%H S. Hougardy, <a href="http://www.or.uni-bonn.de/~hougardy/">Home Page</a>
%H S. Hougardy, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.021">Classes of perfect graphs</a>, Discr. Math. 306 (2006), 2529-2571.
%H ISCGI, <a href="http://www.graphclasses.org/classes/gc_151.html">Cograph graphs</a>
%H Yukinao Isokawa, <a href="http://dx.doi.org/10.12988/ams.2016.63103">Series-Parallel Circuits and Continued Fractions</a>, Applied Mathematical Sciences, Vol. 10, 2016, no. 27, 1321 - 1331.
%H Yukinao Isokawa, <a href="https://ir.kagoshima-u.ac.jp/?action=repository_uri&item_id=12102&file_id=16&file_no=1">Listing up Combinations of Resistances</a>, Bulletin of the Kagoshima University Faculty of Education. Bulletin of the Faculty of Education, Kagoshima University. Natural science, Vol. 67 (2016), pp. 1-8.
%H Sameen Ahmed Khan, <a href="/A048211/a048211.nb">Mathematica notebook for A048211 and A000084</a>
%H Sameen Ahmed Khan, <a href="http://arxiv.org/abs/1004.3346">The bounds of the set of equivalent resistances of n equal resistors combined in series and in parallel</a>, arXiv:1004.3346 [physics.gen-ph], 2010.
%H S. A. Khan, <a href="http://www.ias.ac.in/resonance/May2012/p468-475.pdf">How Many Equivalent Resistances?</a>, RESONANCE, May 2012.
%H S. A. Khan, <a href="http://www.ias.ac.in/mathsci/vol122/may2012/pmsc-d-10-00141.pdf">Farey sequences and resistor networks</a>, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 122, No. 2, May 2012, pp. 153-162. - From _N. J. A. Sloane_, Oct 23 2012
%H Sameen Ahmed Khan, <a href="http://dx.doi.org/10.17485/ijst%2F2016%2Fv9i44%2F88086">Beginning to count the number of equivalent resistances</a>, Indian Journal of Science and Technology, 2016, Vol 9(44).
%H Z. A. Lomnicki, <a href="http://www.jstor.org/stable/1425808">Two-terminal series-parallel networks</a>, Adv. Appl. Prob., 4 (1972), 109-150.
%H P. A. MacMahon, <a href="http://plms.oxfordjournals.org/content/s1-22/1/330.extract">Yoke-trains and multipartite compositions in connexion with the analytical forms called "trees"</a>, Proc. London Math. Soc. 22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616. Page 333 gives A000084 = 2*A000669.
%H P. A. MacMahon, <a href="http://dx.doi.org/10.1016/0166-218X(94)90024-8">The combination of resistances</a>, The Electrician, 28 (1892), 601-602; reprinted in Coll. Papers I, pp. 617-619. Reprinted in Discrete Appl. Math., 54 (1994), 225-228.
%H J. W. Moon, <a href="http://dx.doi.org/10.1016/S0304-0208(08)73057-3">Some enumerative results on series-parallel networks</a>, Annals Discrete Math., 33 (1987), 199-226.
%H David Richter, <a href="https://arxiv.org/abs/2210.12012">Generic Orthotopes</a>, arXiv:2210.12012 [math.CO], 2022.
%H David Richter, <a href="https://arxiv.org/abs/2309.09026">Ehrhart Polynomials of Generic Orthotopes</a>, arXiv:2309.09026 [math.CO], 2023.
%H J. Riordan and C. E. Shannon, <a href="/A000084/a000084_1.pdf">The number of two-terminal series-parallel networks</a> (annotated scanned copy)
%H N. J. A. Sloane, <a href="/A000084/a000084.pdf">Illustrations of a(1)-a(4)</a>
%H N. J. A. Sloane, <a href="/A000669/a000669.txt">First 1001 terms of A000669 and A000084</a>
%H Marx Stampfli, <a href="https://dx.doi.org/10.1016%2Fj.amc.2016.12.030">Bridged graphs, circuits and Fibonacci numbers</a>. Applied Mathematics and Computation. Volume 302, 1 June 2017, Pages 68-79.
%H Takeaki Uno, Ryuhei Uehara and Shin-ichi Nakano, <a href="http://dx.doi.org/10.1007/978-3-642-28076-4_4">Bounding the Number of Reduced Trees, Cographs, and Series-Parallel Graphs by Compression</a>, 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
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Cograph.html">Cograph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Series-ParallelNetwork.html">Series-Parallel Network</a>
%F The sequence satisfies Product_{k>=1} 1/(1-x^k)^A000669(k) = 1 + Sum_{k>=1} a(k)*x^k.
%F a(n) = 2*A000669(n) if n>0. - _Michael Somos_, Apr 17 2014
%F a(n) ~ C d^n/n^(3/2) where C = 0.412762889201578063700271574144..., d = 3.56083930953894332952612917270966777... is a root of Product_{n>=1} (1-1/x^n)^(-a(n)) = 2. - Riordan, Shannon, Moon, Rains, Sloane
%F 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.
%e G.f. = x + 2*x^2 + 4*x^3 + 10*x^4 + 24*x^5 + 66*x^6 + 180*x^7 + 522*x^8 + ...
%e The series-parallel networks with 1, 2 and 3 edges are:
%e 1 edge: o-o
%e 2 edges: o-o-o o=o
%e ....................... /\
%e 3 edges: o-o-o-o o-o=o o--o o-o-o
%e ....................... \/ ..\_/
%p # (continue from A000669):
%p A000084 := n-> if n=1 then 1 else 2*A000669(n); fi;
%p # 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);
%t n = 27; s = 1/(1-x) + O[x]^(n+1); Do[s = s/(1-x^k)^Coefficient[s, x^k] + O[x]^(n+1), {k, 2, n}]; CoefficientList[s, x] // Rest (* _Jean-François Alcover_, Jun 20 2011, updated Jun 30 2015 *)
%t (* faster method: *)
%t 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 *)
%t n = 27; Rest@
%t CoefficientList[ Fold[ #1/(1 - x^#2)^Coefficient[#1, x, #2] &, 1/(1 - x) + O[x]^(n + 1), Range[2, n]], x] (* _Oliver Seipel_, Sep 19 2021 *)
%o (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 */
%Y Cf. A058351, A058352, A058353, A000311, A006351 (labeled version).
%Y See also A058964, A058965, A363065.
%Y Cf. A144962, A001572. - _Gary W. Adamson_, Sep 27 2008
%Y Cf. A176500, A176502. - _Sameen Ahmed Khan_, Apr 27 2010
%K nonn,nice,easy
%O 1,2
%A _N. J. A. Sloane_
%E More decimal places in the third formula added by _Vaclav Kotesovec_, Jun 24 2014
|
