|
%I M1885 #151 Jul 19 2022 02:18:01
%S 1,2,8,52,472,5504,78416,1320064,25637824,564275648,13879795712,
%T 377332365568,11234698041088,363581406419456,12707452084972544,
%U 477027941930515456,19142041172838025216,817675811320888020992,37044610820729973813248,1774189422608238694776832
%N Number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon.
%C For a simple relationship to series-reduced rooted trees, partitions of n, and phylogenetic trees among other combinatoric constructs, see comments in A000311. - _Tom Copeland_, Jan 06 2021
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.
%D 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 P. A. MacMahon, The combination of resistances, The Electrician, 28 (1892), 601-602; reprinted in Coll. Papers I, pp. 617-619.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 142.
%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(a), S(x).
%H Alois P. Heinz, <a href="/A006351/b006351.txt">Table of n, a(n) for n = 1..200</a>
%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
%H P. J. Cameron, <a href="https://doi.org/10.37236/1198">Counting two-graphs related to trees</a>, Elec. J. Combin., Vol. 2, #R4. [From _Aaron Meyerowitz_, Sep 30 2010]
%H F. Chapoton, F. Hivert, and J.-C. Novelli, <a href="http://arxiv.org/abs/1307.0092">A set-operad of formal fractions and dendriform-like sub-operads</a>, arXiv preprint arXiv:1307.0092 [math.CO], 2013
%H D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions</a>, arXiv:math/0501052 [math.CA], 2005.
%H B. Drake, <a href="http://people.brandeis.edu/~gessel/homepage/students/drakethesis.pdf">An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.5.1 )</a>, A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Series-parallel networks</a>
%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 ISCGI, <a href="http://www.graphclasses.org/classes/gc_151.html">Cograph graphs</a>
%H Song He, Fei Teng, and Yong Zhang, <a href="https://arxiv.org/abs/1907.06041">String Correlators: Recursive Expansion, Integration-by-Parts and Scattering Equations</a>, arXiv:1907.06041 [hep-th], 2019. Also in <a href="https://doi.org/10.1007/JHEP09(2019)085">Journal of High Energy Physics</a> (2019), 2019:85.
%H W. Knoedel, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002470373">Über Zerfällungen</a>, Monatsh. Math., 55 (1951), 20-27.
%H Vladimir Kruchinin, <a href="http://arxiv.org/abs/1211.3244">The method for obtaining expressions for coefficients of reverse generating functions</a>, arXiv:1211.3244 [math.CO], 2012.
%H Z. A. Lomnicki, <a href="https://doi.org/10.2307/1425808">Two-terminal series-parallel networks</a>, Adv. Appl. Prob., 4 (1972), 109-150.
%H M. D. Moffitt, <a href="https://doi.org/10.1609/aaai.v36i9.21271">Search Strategies for Topological Network Optimization</a>, Proceedings of the AAAI Conference on Artificial Intelligence, 36(9) (2022), 10299-10308.
%H J. W. Moon, <a href="https://doi.org/10.1016/S0304-0208(08)73057-3">Some enumerative results on series-parallel networks</a>, Annals Discrete Math., 33 (1987), 199-226 (the e.g.f. U(x)).
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H <a href="/index/Res#revert">Index entries for reversions of series</a>
%H <a href="/index/Mo#Moon87">Index entries for sequences mentioned in Moon (1987)</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a> [From _Aaron Meyerowitz_, Sep 30 2010]
%F For n >= 2, A006351(n) = 2*A000311(n) = A005640(n)/2^n. Row sums of A140945.
%F E.g.f. is reversion of 2*log(1+x)-x.
%F Also exponential transform of A000311, define b by 1+sum b_n x^n / n! = exp ( 1 + sum a_n x^n /n!).
%F E.g.f.: A(x), B(x)=x*A(x) satisfies the differential equation B'(x)=(1+B(x))/(1-B(x)). - _Vladimir Kruchinin_, Jan 18 2011
%F From _Peter Bala_, Sep 05 2011: (Start)
%F The generating function A(x) satisfies the autonomous differential equation A'(x) = (1+A)/(1-A) with A(0) = 0. Hence the inverse function A^-1(x) = int {t = 0..x} (1-t)/(1+t) = 2*log(1+x)-x, which yields A(x) = -1-2*W(-1/2*exp((x-1)/2)), where W is the Lambert W function.
%F The expansion of A(x) can be found by inverting the above integral using the method of [Dominici, Theorem 4.1] to arrive at the result a(n) = D^(n-1)(1) evaluated at x = 0, where D denotes the operator g(x) -> d/dx((1+x)/(1-x)*g(x)). Compare with A032188.
%F Applying [Bergeron et al., Theorem 1] to the result x = int {t = 0..A(x)} 1/phi(t), where phi(t) = (1+t)/(1-t) = 1 + 2*t + 2*t^2 + 2*t^3 + ..., leads to the following combinatorial interpretation for the sequence: a(n) gives the number of plane increasing trees on n vertices where each vertex of outdegree k >=1 can be in one of 2 colors. An example is given below. (End)
%F A134991 gives (b.+c.)^n = 0^n , for (b_n)=A000311(n+1) and (c_0)=1, (c_1)=-1, and (c_n)=-2* A000311(n) = -A006351(n) otherwise. E.g., umbrally, (b.+c.)^2 = b_2*c_0 + 2 b_1*c_1 + b_0*c_2 =0. - _Tom Copeland_, Oct 19 2011
%F G.f.: 1/S(0) where S(k) = 1 - x*(k+1) - x*(k+1)/S(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Dec 18 2011
%F a(n) = ((n-1)!*sum(k=1..n-1, C(n+k-1,n-1)*sum(j=1..k, (-1)^(j)*C(k,j)* sum(l=0..j, (C(j,l)*(j-l)!*2^(j-l)*(-1)^l*stirling1(n-l+j-1,j-l))/ (n-l+j-1)!)))), n>1, a(1)=1. - _Vladimir Kruchinin_, Jan 24 2012
%F E.g.f.: A(x) = exp(B(x))-1 where B(x) is the e.g.f. of A000311. - _Vladimir Kruchinin_, Sep 25 2012
%F a(n) = sum_{k=0..n-1} A201637(n-1,k)*2^(n-k-1). - _Peter Luschny_, Nov 16 2012
%F G.f.: -1 + 2/Q(0), where Q(k)= 1 - k*x - x*(k+1)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, May 01 2013
%F a(n) ~ sqrt(2)*n^(n-1)/((2*log(2)-1)^(n-1/2)*exp(n)). - _Vaclav Kotesovec_, Jul 17 2013
%F G.f.: Q(0)/(1-x), where Q(k) = 1 - x*(k+1)/( x*(k+1) - (1 -x*(k+1))*(1 -x*(k+2))/Q(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Oct 10 2013
%F a(1) = 1; a(n) = a(n-1) + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k). - _Ilya Gutkovskiy_, Aug 28 2020
%e D^3(1) = (12*x^2+56*x+52)/(x-1)^6. Evaluated at x = 0 this gives a(4) = 52.
%e a(3) = 8: The 8 possible increasing plane trees on 3 vertices with vertices of outdegree k >= 1 coming in 2 colors, B or W, are
%e .......................................................
%e .1B..1B..1W..1W.....1B.......1W........1B........1W....
%e .|...|...|...|...../.\....../..\....../..\....../..\...
%e .2B..2W..2B..2W...2...3....2....3....3....2....3....2..
%e .|...|...|...|.........................................
%e .3...3...3...3.........................................
%e G.f. = x + 2*x^2 + 8*x^3 + 52*x^4 + 472*x^5 + 5504*x^6 + 78416*x^7 + ...
%p read transforms; t1 := 2*ln(1+x)-x; t2 := series(t1,x,10); t3 := seriestoseries(t2,'revogf'); t4 := SERIESTOLISTMULT(%);
%p # N denotes all series-parallel networks, S = series networks, P = parallel networks;
%p spec := [ N, N=Union(Z,S,P),S=Set(Union(Z,P),card>=2), P=Set(Union(Z,S), card>=2)}, labeled ]: A006351 := n->combstruct[count](spec,size=n);
%p A006351 := n -> add(combinat[eulerian2](n-1,k)*2^(n-k-1),k=0..n-1):
%p seq(A006351(n), n=1..18); # _Peter Luschny_, Nov 16 2012
%t max = 18; f[x_] := 2*Log[1+x]-x; Rest[ CoefficientList[ InverseSeries[ Series[ f[x], {x, 0, max}], x], x]]*Range[max]! (* _Jean-François Alcover_, Nov 25 2011 *)
%o (Maxima) a(n):=if n=1 then 1 else ((n-1)!*sum(binomial(n+k-1,n-1)* sum((-1)^(j)*binomial(k,j)*sum((binomial(j,l)*(j-l)!*2^(j-l)*(-1)^l* stirling1(n-l+j-1,j-l))/(n-l+j-1)!,l,0,j),j,1,k),k,1,n-1)); /* _Vladimir Kruchinin_, Jan 24 2012 */
%o (Sage) # uses[eulerian2 from A201637]
%o def A006351(n): return add(A201637(n-1, k)*2^(n-k-1) for k in (0..n-1))
%o [A006351(n) for n in (1..18)] # _Peter Luschny_, Nov 16 2012
%o (PARI) x='x+O('x^66); Vec(serlaplace(serreverse( 2*log(1+x) - 1*x ))) \\ _Joerg Arndt_, May 01 2013
%Y Cf. A000311, A000084 (for unlabeled case), A032188. A140945.
%Y Cf. A133314, A134991, A135494.
%K nonn,easy,nice
%O 1,2
%A _N. J. A. Sloane_
| 