A339228 -id:A339228 - cp's OEIS frontend

A003430 Number of unlabeled series-parallel posets (i.e., generated by unions and sums) with n nodes.

1, 1, 2, 5, 15, 48, 167, 602, 2256, 8660, 33958, 135292, 546422, 2231462, 9199869, 38237213, 160047496, 674034147, 2854137769, 12144094756, 51895919734, 222634125803, 958474338539, 4139623680861, 17931324678301, 77880642231286, 339093495674090, 1479789701661116

Offset: 0

N. J. A. Sloane, Richard Stanley, and Mira Bernstein

Number of oriented series-parallel networks with n elements. A series configuration is a unit element or an ordered concatenation of two or more parallel configurations and a parallel configuration is a unit element or a multiset of two or more series configurations. a(n) is the number of series or parallel configurations with n elements. The sequences A007453 and A007454 enumerate respectively series and parallel configurations. - Andrew Howroyd, Dec 01 2020

			From _Andrew Howroyd_, Nov 26 2020: (Start)
In the following examples of series-parallel networks, elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element is denoted by 'o'.
a(1) = 1: (o).
a(2) = 2: (oo), (o|o).
a(3) = 5: (ooo), (o(o|o)), ((o|o)o), (o|o|o), (o|oo).
a(4) = 15: (oooo), (oo(o|o)), (o(o|o)o), ((o|o)oo), ((o|o)(o|o)), (o(o|oo)), (o(o|o|o)), ((o|oo)o), ((o|o|o)o), (o|o|o|o), (o|o|oo), (oo|oo), (o|ooo), (o|o(o|o)), (o|(o|o)o).
(End)

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.39 (which deals with the labeled case of the same sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n = 1..100 from Jean-François Alcover)
B. I. Bayoumi, M. H. El-Zahar and S. M. Khamis, Asymptotic enumeration of N-free partial orders, Order 6 (1989), 219-232.
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.
Uli Fahrenberg, Christian Johansen, Georg Struth, Ratan Bahadur Thapa, Generating Posets Beyond N, arXiv:1910.06162 [cs.FL], 2019.
Frédéric Fauvet, L. Foissy, D. Manchon, Operads of finite posets, arXiv preprint arXiv:1604.08149 [math.CO], 2016.
S. R. Finch, Series-parallel networks
S. R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 72.
Soheir M. Khamis, Height counting of unlabeled interval and N-free posets, Discrete Math. 275 (2004), no. 1-3, 165-175.
R. P. Stanley, Enumeration of posets generated by disjoint unions and ordinal sums, Proc. Amer. Math. Soc. 45 (1974), 295-299. Math. Rev. 50 #4416.
R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
Index entries for sequences related to posets

Row sums of A339231.
Column k=1 of A339228.
Cf. A000084, A003431, A048172 (labeled N-free posets), A007453, A007454, A339156, A339159, A339225.

terms = 25; A[] = 1; Do[A[x] = Exp[Sum[(1/k)*(A[x^k] + 1/A[x^k] - 2 + x^k), {k, 1, terms + 1}]] + O[x]^(terms + 1) // Normal, terms + 1];
CoefficientList[A[x], x] // Rest (* Jean-François Alcover, Jun 29 2011, updated Jan 12 2018 *)

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(p=x+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+x, 1-n)))); Vec(p)} \\ Andrew Howroyd, Nov 27 2020

G.f. A(x) = 1 + x + 2*x^2 + 5*x^3 + ... satisfies A(x) = exp(Sum_{k>=1} (1/k)*(A(x^k) + 1/A(x^k) - 2 + x^k)).
From: Andrew Howroyd, Nov 26 2020: (Start)
a(n) = A007453(n) + A007454(n) for n > 1.
Euler transform of A007453.
G.f.: P(x)/(1 - P(x)) where P(x) is the g.f. of A007454.
(End)

Name corrected by Salah Uddin Mohammad, Jun 07 2020

a(0)=1 prepended (using the g.f.) by Alois P. Heinz, Dec 01 2020

A339282 Triangle read by rows: T(n,k) is the number of unoriented series-parallel networks with n colored elements using exactly k colors.

Original entry on oeis.org

1, 2, 2, 4, 14, 10, 11, 84, 168, 98, 30, 522, 2109, 3004, 1396, 98, 3426, 24397, 63094, 67660, 25652, 328, 23404, 274626, 1142420, 2119985, 1805082, 576010, 1193, 165417, 3065376, 19230320, 54916745, 78809079, 55503392, 15282038, 4459, 1197934, 34201068, 311157620, 1283360335, 2761083930, 3220245007, 1932118328, 467747416

Offset: 1

Andrew Howroyd, Nov 30 2020

Unoriented version of A339228. Equivalence is up to reversal of all parts combined in series.

			Triangle begins:
    1;
    2,     2;
    4,    14,     10;
   11,    84,    168,      98;
   30,   522,   2109,    3004,    1396;
   98,  3426,  24397,   63094,   67660,   25652;
  328, 23404, 274626, 1142420, 2119985, 1805082, 576010;
  ...

Columns 1..2 are A339225, A339281.
Row sums are A339283.
Cf. A339228, A339280, A339285.

\\ R(n, k) gives colorings using at most k colors as a vector.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
B(n, Z)={my(p=Z+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+Z)))); p}
R(n,k)={my(Z=k*x, q=subst(B((n+1)\2, Z), x, x^2), s=subst(Z,x,x^2)+q^2/(1+q), p=Z+O(x^2), t=p); for(n=1, n\2, t=Z + q*(1 + p); p=Z + x*Ser(EulerT(Vec(t+(s-subst(t, x, x^2))/2))) - t); Vec(p+t-Z+B(n,Z))/2}
M(n)={my(v=vector(n, k, R(n, k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k, i)*v[i])))}
{my(T=M(8)); for(n=1, #T~, print(T[n, 1..n]))}

A339229 Number of oriented series-parallel networks with n integer valued elements spanning an initial interval of positive integers.

Original entry on oeis.org

1, 5, 46, 677, 13897, 367329, 11875112, 453884998, 20021744482, 1001103144204, 55950350379398, 3456387167052662, 233868854544617505, 17200896572547662922, 1366363690436820691346, 116580486267706011046208, 10633034275200701222560393, 1032398637197381396948606128

Offset: 1

Andrew Howroyd, Nov 28 2020

nonn

See A339228 for additional details.

			In the following examples elements in series are juxtaposed and elements in parallel are separated by '|'.
a(1) = 1: (1).
a(2) = 5: (11), (12), (21), (1|1), (1|2).

Row sums of A339228.

\\ See A339228 for R(n,k).
seq(n)={sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) )}

A339226 Number of oriented series-parallel networks with n elements of 2 colors.

Original entry on oeis.org

2, 7, 32, 176, 1066, 6935, 47216, 332700, 2404818, 17734668, 132901644, 1009161505, 7747608480, 60037905076, 468987635982, 3689066578347, 29195587558726, 232303316402615, 1857264782113562, 14912673794505898, 120203145484455930, 972291038495626309

Offset: 1

Andrew Howroyd, Nov 28 2020

nonn

See A339228 for additional details.

			In the following examples elements in series are juxtaposed and elements in parallel are separated by '|'.
a(1) = 2: (1), (2).
a(2) = 7: (11), (12), (21), (22), (1|1), (1|2), (2|2).

Cf. A003430, A339227, A339228.

\\ See A339228 for R(n,k).
seq(n) = {R(n,2)}

A339227 Number of oriented series-parallel networks with n colored elements using exactly 2 colors.

Original entry on oeis.org

0, 3, 22, 146, 970, 6601, 46012, 328188, 2387498, 17666752, 132631060, 1008068661, 7743145556, 60019505338, 468911161556, 3688746483355, 29194239490432, 232297608127077, 1857240493924050, 14912570002666430, 120202700216204324, 972289121546949231

Offset: 1

Andrew Howroyd, Nov 28 2020

nonn

See A339228 for additional details.

			In the following examples elements in series are juxtaposed and elements in parallel are separated by '|'.
a(2) = 3: (12), (21), (22), (1|2).
a(3) = 22: (112), (121), (122), (211), (212), (221), (1(1|2)), (1(2|2)), (2(1|1)), (2(1|2)), ((1|1)2), ((1|2)1), ((1|2)2), ((2|2)1), (1|12), (1|21), (1|22), (2|21), (11|2), (12|2), (1|1|2), (1|2|2).

Column k=2 of A339228.

Cf. A003430, A339226.

\\ See A339228 for R(n,k).
seq(n) = {R(n,2) - 2*R(n,1)}

a(n) = A339226(n) - 2*A003430(n).

A339231 Triangle read by rows: T(n,k) is the number of oriented series-parallel networks whose multigraph has n edges and k interior vertices, 0 <= k < n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 7, 1, 1, 10, 23, 13, 1, 1, 15, 59, 69, 22, 1, 1, 21, 124, 249, 172, 34, 1, 1, 28, 234, 711, 853, 378, 50, 1, 1, 36, 402, 1733, 3175, 2487, 755, 70, 1, 1, 45, 650, 3755, 9767, 11813, 6431, 1400, 95, 1, 1, 55, 995, 7443, 26043, 44926, 38160, 15098, 2445, 125, 1

Offset: 1

Andrew Howroyd, Nov 29 2020

A series configuration is a unit element or an ordered concatenation of two or more parallel configurations and a parallel configuration is a unit element or a multiset of two or more series configurations. T(n, k) is the number of series or parallel configurations with n unit elements whose representation as a multigraph has k interior vertices, with elements corresponding to edges. Parallel configurations do not increase the interior vertex count and series configurations increase it by one less than the number of parts.

			Triangle begins:
  1;
  1,  1;
  1,  3,   1;
  1,  6,   7,   1;
  1, 10,  23,  13,   1;
  1, 15,  59,  69,  22,   1;
  1, 21, 124, 249, 172,  34,  1;
  1, 28, 234, 711, 853, 378, 50, 1;
  ...
In the following examples elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element is denoted by 'o'.
T(4,0) = 1: (o|o|o|o).
T(4,1) = 6: ((o|o)(o|o)), (o(o|o|o)), ((o|o|o)o), (o|o|oo), (o|o(o|o)), (o|(o|o)o).
T(4,2) = 7: (oo(o|o)), (o(o|o)o), ((o|o)oo),  (o(o|oo)), ((o|oo)o),  (oo|oo), (o|ooo).
T(4,3) = 1: (oooo).
The graph of (oo(o|o)) has 4 edges (elements) and 2 interior vertices as shown below:
      A---o---o===Z (where === is a double edge).

Row sums are A003430.

Cf. A002623, A339228, A339230, A339232.

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, [v^i|v<-vars])/i ))-1)}
VertexWeighted(n, W)={my(Z=x, p=Z+O(x^2)); for(n=2, n, p=x*Ser(EulerMT(Vec(W*p^2/(1 + W*p) + Z)))); Vec(p)}
T(n)={[Vecrev(p)|p<-VertexWeighted(n,y)]}
{ my(A=T(12)); for(n=1, #A, print(A[n])) }

T(n,0) = T(n,n-1) = 1.
T(n,1) = binomial(n,2).
T(n+2,n) = A002623(n).
Sum_{k=1..n-1} k*T(n,k) = A339232(n).

A339230 Number of oriented series-parallel networks with integer valued elements summing to n.

Original entry on oeis.org

1, 3, 9, 32, 120, 490, 2077, 9158, 41401, 191232, 897849, 4273794, 20573696, 99994830, 490000756, 2418246995, 12008813611, 59962351145, 300864703306, 1516196518032, 7670827035223, 38946578808655, 198379559337073, 1013452414823740, 5191372465942866, 26658747310696437

Offset: 1

Andrew Howroyd, Nov 29 2020

nonn

See A339228 for additional details.

			In the following examples elements in series are juxtaposed and elements in parallel are separated by '|'.
a(1) = 1: (1).
a(2) = 3: (2), (11), (1|1).
a(3) = 9: (3), (12), (21), (1(1|1)), ((1|1)1), (111), (1|2), (1|11), (1|1|1).

Cf. A339228, A339229.

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
EdgeWeightedT(u)={my(Z=x*Ser(u)); my(p=Z+O(x^2)); for(n=2, #u, p=x*Ser(EulerT(Vec(p^2/(1+p)+Z)))); Vec(p)}
seq(n)={EdgeWeightedT(vector(n,i,1))}

A339297 Triangle read by rows: T(n,k) is the number of oriented series-parallel networks with n colored elements and without multiple unit elements in parallel using exactly k colors.

Original entry on oeis.org

1, 1, 2, 2, 12, 12, 5, 64, 162, 108, 13, 354, 1734, 2760, 1380, 36, 1992, 16977, 48716, 56100, 22440, 103, 11538, 161691, 746316, 1488240, 1338120, 446040, 306, 68427, 1524969, 10652086, 32760180, 49718640, 36614760, 10461360, 930, 414294, 14382720, 146464740, 652517010, 1487453760, 1816345440, 1131883200, 282970800

Offset: 1

Andrew Howroyd, Dec 22 2020

A series configuration is an ordered concatenation of two or more parallel configurations and a parallel configuration is a multiset of two or more unit elements or series configurations. In this variation, parallel configurations may include the unit element only once. T(n, k) is the number of series or parallel configurations with n unit elements of k colors using each color at least once.

			Triangle begins:
    1;
    1,     2;
    2,    12,     12;
    5,    64,    162,    108;
   13,   354,   1734,   2760,    1380;
   36,  1992,  16977,  48716,   56100,   22440;
  103, 11538, 161691, 746316, 1488240, 1338120, 446040;
  ...

Column 1 is A339290.
Main diagonal is A339301.
Row sums are A339298.
Cf. A339228.

\\ R(n, k) gives colorings using at most k colors as a vector.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n, k)={my(Z=k*x, p=Z+O(x^2)); for(n=2, n, p = Z + (1 + Z)*x*Ser(EulerT( Vec(p^2/(1+p), -n) ))); Vec(p)}
M(n)={my(v=vector(n, k, R(n, k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k, i)*v[i])))}
{my(T=M(8)); for(n=1, #T~, print(T[n, 1..n]))}

A339233 Number of inequivalent colorings of oriented series-parallel networks with n colored elements.

Original entry on oeis.org

1, 4, 21, 165, 1609, 19236, 266251, 4175367, 72705802, 1387084926, 28689560868, 638068960017, 15158039092293, 382527449091778, 10207466648995608, 286876818184163613, 8462814670769394769, 261266723355912507073, 8419093340955799898258, 282519424041100564770142

Offset: 1

Andrew Howroyd, Dec 22 2020

nonn

Equivalence is up to permutation of the colors. Any number of colors may be used. See A339228 for additional details.

			In the following examples elements in series are juxtaposed and elements in parallel are separated by '|'.
a(1) = 1: (1).
a(2) = 4: (11), (12), (1|1), (1|2).
a(3) = 21: (111), (112), (121), (122), (123), (1(1|1)), (1(1|2)), (1(2|2)), (1(2|3)), ((1|1)1), ((1|1)2), ((1|2)1), ((1|2)3), (1|1|1), (1|1|2), (1|2|3), (1|11), (1|12), (1|21), (1|22), (1|23).

Cf. A003430 (uncolored), A339226, A339228, A339229, A339287 (unoriented), A339645.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(Z=x*sv(1), p=Z+O(x^2)); for(n=2, n, p=sEulerT(p^2/(1+p) + Z)-1); p}
InequivalentColoringsSeq(cycleIndexSeries(15))

cp's OEIS Frontend

A003430 Number of unlabeled series-parallel posets (i.e., generated by unions and sums) with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A339282 Triangle read by rows: T(n,k) is the number of unoriented series-parallel networks with n colored elements using exactly k colors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A339229 Number of oriented series-parallel networks with n integer valued elements spanning an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A339226 Number of oriented series-parallel networks with n elements of 2 colors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A339227 Number of oriented series-parallel networks with n colored elements using exactly 2 colors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A339231 Triangle read by rows: T(n,k) is the number of oriented series-parallel networks whose multigraph has n edges and k interior vertices, 0 <= k < n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A339230 Number of oriented series-parallel networks with integer valued elements summing to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A339297 Triangle read by rows: T(n,k) is the number of oriented series-parallel networks with n colored elements and without multiple unit elements in parallel using exactly k colors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI