A379460 -id:A379460 - cp's OEIS frontend

A006351 Number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon.

1, 2, 8, 52, 472, 5504, 78416, 1320064, 25637824, 564275648, 13879795712, 377332365568, 11234698041088, 363581406419456, 12707452084972544, 477027941930515456, 19142041172838025216, 817675811320888020992, 37044610820729973813248, 1774189422608238694776832

Offset: 1

N. J. A. Sloane

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^3(1) = (12*x^2+56*x+52)/(x-1)^6. Evaluated at x = 0 this gives a(4) = 52.
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
.......................................................
.1B..1B..1W..1W.....1B.......1W........1B........1W....
.|...|...|...|...../.\....../..\....../..\....../..\...
.2B..2W..2B..2W...2...3....2....3....3....2....3....2..
.|...|...|...|.........................................
.3...3...3...3.........................................
G.f. = x + 2*x^2 + 8*x^3 + 52*x^4 + 472*x^5 + 5504*x^6 + 78416*x^7 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.
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.
P. A. MacMahon, The combination of resistances, The Electrician, 28 (1892), 601-602; reprinted in Coll. Papers I, pp. 617-619.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 142.
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(a), S(x).

Alois P. Heinz, Table of n, a(n) for n = 1..200
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
Veronica Bitonti, Bishal Deb, and Alan D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, arXiv:2412.10214 [math.CO], 2024. See p. 58.
Peter J. Cameron, Counting two-graphs related to trees, Elec. J. Combin., Vol. 2, #R4. [From _Aaron Meyerowitz_, Sep 30 2010]
Frédéric Chapoton, Florent Hivert, and Jean-Christophe Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013
Diego Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions, arXiv:math/0501052 [math.CA], 2005.
Brian Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.5.1 ), Ph. D. dissertation, Brandeis Univ., 2008.
Steven R. Finch, Series-parallel networks
Steven R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
ISCGI, Cograph graphs
Song He, Fei Teng, and Yong Zhang, String Correlators: Recursive Expansion, Integration-by-Parts and Scattering Equations, arXiv:1907.06041 [hep-th], 2019. Also in Journal of High Energy Physics (2019), 2019:85.
Walter Knödel, Über Zerfällungen, Monatsh. Math., 55 (1951), 20-27.
Vladimir Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244 [math.CO], 2012.
Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.
Michael D. Moffitt, Search Strategies for Topological Network Optimization, Proceedings of the AAAI Conference on Artificial Intelligence, 36(9) (2022), 10299-10308.
John W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226 (the e.g.f. U(x)).
N. J. A. Sloane, Transforms
Index entries for reversions of series
Index entries for sequences mentioned in Moon (1987)
Index entries for sequences related to trees [From _Aaron Meyerowitz_, Sep 30 2010]

Cf. A000311, A000084 (for unlabeled case), A032188. A140945.

Cf. A133314, A134991, A135494.

read transforms; t1 := 2*ln(1+x)-x; t2 := series(t1,x,10); t3 := seriestoseries(t2,'revogf'); t4 := SERIESTOLISTMULT(%);
# N denotes all series-parallel networks, S = series networks, P = parallel networks;
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);
A006351 := n -> add(combinat[eulerian2](n-1,k)*2^(n-k-1),k=0..n-1):
seq(A006351(n), n=1..18); # Peter Luschny, Nov 16 2012

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 *)

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 */

x='x+O('x^66); Vec(serlaplace(serreverse( 2*log(1+x) - 1*x ))) \\ Joerg Arndt, May 01 2013

# uses[eulerian2 from A201637]
def A006351(n): return add(A201637(n-1, k)*2^(n-k-1) for k in (0..n-1))
[A006351(n) for n in (1..18)]  # Peter Luschny, Nov 16 2012

For n >= 2, A006351(n) = 2*A000311(n) = A005640(n)/2^n. Row sums of A140945.
E.g.f. is reversion of 2*log(1+x)-x.
Also exponential transform of A000311, define b by 1+sum b_n x^n / n! = exp ( 1 + sum a_n x^n /n!).
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
From Peter Bala, Sep 05 2011: (Start)
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.
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.
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)
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
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
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
E.g.f.: A(x) = exp(B(x))-1 where B(x) is the e.g.f. of A000311. - Vladimir Kruchinin, Sep 25 2012
a(n) = sum_{k=0..n-1} A201637(n-1,k)*2^(n-k-1). - Peter Luschny, Nov 16 2012
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
a(n) ~ sqrt(2)*n^(n-1)/((2*log(2)-1)^(n-1/2)*exp(n)). - Vaclav Kotesovec, Jul 17 2013
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
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
Conjecture: a(n) = A379459(n-2,0) = A379460(n-1,0) for n > 1 with a(1) = 1. - Mikhail Kurkov, Jan 16 2025

A298673 Inverse matrix of A135494.

Original entry on oeis.org

1, 1, 1, 4, 3, 1, 26, 19, 6, 1, 236, 170, 55, 10, 1, 2752, 1966, 645, 125, 15, 1, 39208, 27860, 9226, 1855, 245, 21, 1, 660032, 467244, 155764, 32081, 4480, 434, 28, 1, 12818912, 9049584, 3031876, 635124, 92001, 9576, 714, 36, 1, 282137824, 198754016, 66845340, 14180440, 2108085, 230097, 18690, 1110, 45, 1

Offset: 1

Tom Copeland, Jan 24 2018

Since this is the inverse matrix of A135494 with row polynomials q_n(t), first introduced in that entry by R. J. Mathar, and the row polynomials p_n(t) of this entry are a binomial Sheffer polynomial sequence, the row polynomials of the inverse pair are umbral compositional inverses, i.e., p_n(q.(t)) = q_n(p.(t)) = t^n. For example, p_3(q.(t)) = 4q_1(t) + 3q_2(t) + q_3(t) = 4t + 3(-t + t^2) + (-t -3t^2 +t^3) = t^3. In addition, both sequences possess the umbral convolution property (p.x) + p.(y))^n = p_n(x+y) with p_0(t) = 1.

This is the inverse of the Bell matrix generated by A153881; for the definition of the Bell matrix see the link. - Peter Luschny, Jan 26 2018

			Matrix begins as
     1;
     1;    1;
     4,    3,    1;
    26,   19,    6,    1;
   236,  170,   55,   10,    1;
  2752, 1966,  645,  125,   15,    1;

Peter Luschny, The Bell transform
Andrew Elvey Price and Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.

Cf. A000311, A000169, A000670, A006351, A135494.

# The function BellMatrix is defined in A264428. Adds (1,0,0,0, ..) as column 0.
BellMatrix(n -> `if`(n=0, 1, -1), 9): MatrixInverse(%); # Peter Luschny, Jan 26 2018

BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
B = BellMatrix[Function[n, If[n == 0, 1, -1]], rows = 12] // Inverse;
Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 28 2018, after Peter Luschny *)

E.g.f.: e^[p.(t)x] = e^[t*h(x)] = exp[t*[(x-1)/2 + T{ (1/2) * exp[(x-1)/2] }], where T is the tree function of A000169 related to the Lambert function. h(x) = sum(j=1,...) A000311(j) * x^j / j! = exp[xp.'(0)], so the first column of this entry's matrix is A000311(n) for n > 0 and the second column of the full matrix for p_n(t) to n >= 0. The compositional inverse of h(x) is h^(-1)(x) = 1 + 2x - e^x.
The lowering operator is L = h^(-1)(D) = 1 + 2D - e^D with D = d/dt, i.e., L p_n(t) = n * p_(n-1)(t). For example, L p_3(t) = (D - D^2! - D^3/3! - ...) (4t + 6t^ + t^3) = 3 (t + t^2) = 3 p_2(t).
The raising operator is R = t * 1/[d[h^(-1)(D)]/dD] = t * 1/[2 - e^D)] = t (1 + D + 3D^2/2! + 13D^3/3! + ...). The coefficients of R are A000670. For example, R p_2(t) = t (1 + D + 3D^2/2!  + ...)  (t + t^2) = 4t + 3t^2 + t^3   = p_3(t).
The row sums are A006351, or essentially 2*A000311.
Conjectures from Mikhail Kurkov, Mar 01 2025: (Start)
T(n,k) = Sum_{j=0..n-k} binomial(n+j-1, k-1)*A269939(n-k, j) for 1 <= k <= n.
T(n,k) = A(n-1,k,0) for n > 0, k > 0 where A(n,k,q) = A(n-1,k,q+1) + 2*(q+1)!*Sum_{j=0..q} A(n-1,k,j)/j! for n >= 0, k > 0, q >= 0 with A(0,k,q) = Stirling1(q+1,k) for k > 0, q >= 0 (see A379458). In other words, T(n,k) = Sum_{j=0}^{n-1} A379460(n-j-1,j)*Stirling1(j+1,k) for n > 0, k > 0.
Recursion for the n-th row (independently of other rows): T(n,k) = 1/(n-k)*Sum_{j=2..n-k+1} b(j-1)*binomial(-k,j)*T(n,k+j-1)*(-1)^j for 1 <= k < n with T(n,n) = 1 where b(n) = 1 + 4*Sum_{i=1..n} A135148(i).
Recursion for the k-th column (independently of other columns): T(n,k) = 1/(n-k)*Sum_{j=2..n-k+1} c(j-1)*binomial(n,j)*T(n-j+1,k) for 1 <= k < n with T(n,n) = 1 where c(n) = A000311(n+1) + (n-1)*A000311(n). (End)

cp's OEIS Frontend

A006351 Number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Sage

Formula