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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000669 Number of series-reduced planted trees with n leaves. Also the number of essentially series series-parallel networks with n edges; also the number of essentially parallel series-parallel networks with n edges.
(Formerly M1421 N0558)
34
1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, 218751, 699534, 2253676, 7305788, 23816743, 78023602, 256738751, 848152864, 2811996972, 9353366564, 31204088381, 104384620070, 350064856815, 1176693361956, 3963752002320 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

A cograph is a simple graph which contains no path of length 3 as an induced subgraph. - Michael Somos, Apr 19 2014

REFERENCES

N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 43.

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.

A. Cayley, Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 3, p. 246.

V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012; http://www.math.sc.edu/~czabarka/JohnsonThesis.pdf. - From N. J. A. Sloane, Dec 22 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.

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. Reprinted in Discrete Appl. Math., 54 (1994), 225-228.

L. F. Meyers, Corrections and additions to Tree Representations in Linguistics. Report 3, 1966, p. 138. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.

L. F. Meyers and W. S.-Y. Wang, Tree Representations in Linguistics. Report 3, 1963, pp. 107-108. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.

V. Modrak, D. Marton, Development of Metrics and a Complexity Scale for the Topology of Assembly Supply Chains, Entropy 2013, 15, 4285-4299; doi:10.3390/e15104285

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

J. Riordan and C. E. Shannon, The number of two-terminal series-parallel networks, J. Math. Phys., 21 (1942), 83-93 (the numbers called a_n in this paper). 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).

LINKS

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

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

P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. See pp. 162, 165, 172.

S. R. Finch, Series-parallel networks

Philippe Flajolet, A Problem in Statistical Classification Theory

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 72

Daniel L. Geisler, Combinatorics of Iterated Functions

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 44

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

Index entries for sequences related to rooted trees

Index entries for sequences mentioned in Moon (1987)

Index entries for sequences related to trees

FORMULA

Product_{k>0} 1/(1-x^k)^a_k = 1+x+2*Sum_{k>1} a_k*x^k.

EXAMPLE

a(4)=5 with the following series-reduced planted trees: (oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ((oo)(oo)).

G.f. = x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 33*x^6 + 90*x^7 + 261*x^8 + ...

MAPLE

Method 1: a := [1, 1]; for n from 3 to 30 do L := series( mul( (1-x^k)^(-a[k]), k=1..n-1)/(1-x^n)^b, x, n+1); t1 := coeff(L, x, n); R := series( 1+2*add(a[k]*x^k, k=1..n-1)+2*b*x^n, x, n+1); t2 := coeff(R, x, n); t3 := solve(t1-t2, b); a := [op(a), t3]; od: A000669 := n-> a[n];

Method 2, more efficient: with(numtheory): M := 1001; a := array(0..M); p := array(0..M); a[1] := 1; a[2] := 1; a[3] := 2; p[1] := 1; p[2] := 3; p[3] := 7;

Method 2, cont.: for m from 4 to M do t1 := divisors(m); t3 := 0; for d in t1 minus {m} do t3 := t3+d*a[d]; od: t4 := p[m-1]+2*add(p[k]*a[m-k], k=1..m-2)+t3; a[m] := t4/m; p[m] := t3+t4; od: # A000669 := n-> a[n]; A058757 := n->p[n];

MATHEMATICA

a[1] = 1; a[n_] := (s = Series[1/(1 - x), {x, 0, n}];

Do[s = Series[s/(1 - x^k)^Coefficient[s, x^k], {x, 0, n}], {k, 2, n}]; Coefficient[s, x^n]/2); Array[a, 28]

(* Jean-Fran├žois Alcover, Jun 24 2011, after PARI prog. *)

PROG

(PARI) {a(n) = local(A, X); if( n<2, n>0, X = x + x * O(x^n); A = 1 / (1 - X); for(k=2, n, A /= (1 - X^k)^polcoeff(A, k)); polcoeff(A, n)/2)};

CROSSREFS

Equals (1/2)*A000084 for n >= 2. Cf. A000055, A000311, A001678, A007827.

Cf. A000311, labeled hierarchies on n points.

Sequence in context: A000560 A212823 A032124 * A191769 A221206 A225616

Adjacent sequences:  A000666 A000667 A000668 * A000670 A000671 A000672

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane, John Riordan

EXTENSIONS

Sequence cross reference fixed by Sean A. Irvine, Sep 15 2009

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 August 20 02:49 EDT 2014. Contains 245794 sequences.