%I A000084 M1207 N0466
%S A000084 1,2,4,10,24,66,180,522,1532,4624,14136,43930,137908,437502,1399068,
%T A000084 4507352,14611576,47633486,156047204,513477502,1696305728,5623993944,
%U A000084 18706733128,62408176762,208769240140,700129713630,2353386723912
%N A000084 Number of series-parallel networks with n unlabeled edges. Also called
yoke-chains by Cayley and MacMahon.
%C A000084 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 A000084 Also the number of unlabeled cographs on n nodes. - N. J. A. Sloane (njas(AT)research.att.com)
and Eric W Weisstein, Oct 21, 2003.
%C A000084 Also the number of P_4-free graphs on n nodes. - Gordon Royle, Jul 04
2008
%C A000084 Equals row sums of triangle A144962 and the INVERT transform of A001572.
[From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 27 2008]
%D A000084 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A000084 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973
(includes this sequence).
%D A000084 A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey,
SIAM Publications, 1999. (For definition of cograph)
%D A000084 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.
%D A000084 S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
%D A000084 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 A000084 Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob.,
4 (1972), 109-150.
%D A000084 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.
%D A000084 P. A. MacMahon, The combination of resistances, The Electrician, 28 (1892),
601-602; reprinted in Coll. Papers I, pp. 617-619.
%D A000084 J. W. Moon, Some enumerative results on series-parallel networks, Annals
Discrete Math., 33 (1987), 199-226.
%D A000084 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p.
142.
%D A000084 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 A000084 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see
Problem 5.40, notes on p. 133.
%H A000084 N. J. A. Sloane, <a href="b000084.txt">Table of n, a(n) for n=1..1001</
a>
%H A000084 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
Sequences realized by oligomorphic permutation groups</a>, J. Integ.
Seqs. Vol. 3 (2000), #00.1.5.
%H A000084 S. R. Finch, <a href="http://algo.inria.fr/bsolve/">Series-parallel networks</
a>
%H A000084 O. Golinelli, <a href="http://arXiv.org/abs/cond-mat/9707023">Asymptotic
behavior of two-terminal series-parallel networks</a>.
%H A000084 S. Hougardy, <a href="http://www2.informatik.hu-berlin.de/~hougardy/">
Home Page</a>
%H A000084 N. J. A. Sloane, <a href="a669.txt">First 1001 terms of A000669 and A000084</
a>
%H A000084 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
Cograph.html">Cograph</a>
%H A000084 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
Series-ParallelNetwork.html">Series-Parallel Network</a>
%F A000084 Let b(1)=1, b(n)=a(n)/2 for n >= 2. Then sequence satisfies Product_{k=1..inf}
1/(1-x^k)^b(k) = 1 + Sum_{k=1..inf} a(k)*x^k.
%F A000084 a(n) ~ C d^n/n^(3/2) where C = 0.4126..., d = 3.560839309538943329526...
is a root of Prod_{ n >= 1} (1-1/x^n)^(-a(n)) = 2. - Riordan, Shannon,
Moon, Rains, Sloane
%F A000084 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 A000084 The series-parallel networks with 1, 2 and 3 edges are:
%e A000084 1 edge: o-o
%e A000084 2 edges: o-o-o o=o
%e A000084 ....................... /\
%e A000084 3 edges: o-o-o-o o-o=o o--o o-o-o
%e A000084 ....................... \/ ..\_/
%p A000084 (continue from A000669) A000084 := n-> if n=1 then 1 else 2*A000669(n);
fi;
%p A000084 # 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);
%o A000084 (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 */
%Y A000084 Apart from initial term, 2*A000669. Cf. A058351, A058352, A058353, A000311,
A006351 (labeled version).
%Y A000084 See also A058964, A058965.
%Y A000084 A144962, A001572 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 27
2008]
%Y A000084 Sequence in context: A049146 A000682 A001997 this_sequence A057734 A003104
A151516
%Y A000084 Adjacent sequences: A000081 A000082 A000083 this_sequence A000085 A000086
A000087
%K A000084 nonn,nice,easy
%O A000084 1,2
%A A000084 N. J. A. Sloane (njas(AT)research.att.com).
|
