A007453 -id:A007453 - 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

A007454 Number of unlabeled disconnected series-parallel posets with n nodes.

Original entry on oeis.org

1, 1, 2, 6, 18, 64, 227, 856, 3280, 12885, 51342, 207544, 847886, 3497384, 14541132, 60884173, 256480895, 1086310549, 4623128656, 19759964149, 84784735379, 365066645854, 1576927900803, 6831518134251, 29674505668536, 129216630647787, 563949605921815

Offset: 1

N. J. A. Sloane, Mira Bernstein

nonn

a(1) = 0 would make more sense, but original article has a(1) = 1. - Sean A. Irvine, Jan 04 2018

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 100 terms from Jean-François Alcover)
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
Index entries for sequences related to posets

Cf. A003430, A007453.

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];
A003430 = CoefficientList[A[x], x] // Rest;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
Join[{1}, Rest[A003430 - EULERi[A003430]]] (* Jean-François Alcover, Jan 23 2020 *)

a(n) = A003430(n) - A007453(n) for n > 1. - Sean A. Irvine, Jan 04 2018

Name corrected by Salah Uddin Mohammad, Jun 07 2020

A339157 Number of essentially series achiral series-parallel networks with n elements.

Original entry on oeis.org

1, 1, 1, 3, 4, 11, 17, 46, 78, 203, 372, 946, 1830, 4561, 9207, 22609, 47166, 114514, 245154, 590345, 1289950, 3087959, 6858746, 16352074, 36800928, 87502317, 199036637, 472483088, 1084108363, 2571356964, 5942191918, 14090541799, 32754720101, 77684033014, 181473276607

Offset: 1

Andrew Howroyd, Nov 27 2020

nonn

A series configuration is the unit element or an ordered concatenation of two or more parallel configurations and a parallel configuration is the unit element or a multiset of two or more series configurations. a(n) is the number of series configurations with n unit elements that are invariant under the reversal of all contained series configurations.

			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) = 1: (oo).
a(3) = 1: (ooo).
a(4) = 3: (oooo), ((o|o)(o|o)), (o(o|o)o).
a(5) = 4: (ooooo), ((o|o)o(o|o)), (o(o|oo)o), (o(o|o|o)o).
a(6) = 11: (oooooo), ((o|o)oo(o|o)), (o(o|o)(o|o)o), ((o|oo)(o|oo)), ((o|o|o)(o|o|o)), (oo(o|o)oo), ((o|o)(o|o)(o|o)), (o(o|ooo)o), (o(oo|oo)o), (o(o|o|oo)o), (o(o|o|o|o)o).

Cf. A003430, A007453 (oriented), A339158, A339159, A339223 (unoriented).

\\ here B(n) gives A003430 as a power series.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
B(n)={my(p=x+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+x)))); p}
seq(n)={my(q=subst(B((n+1)\2), x, x^2), s=x^2+q^2/(1+q), p=x+O(x^2)); for(n=1, n\2, p = x + q*(1 + x + x*Ser(EulerT(Vec(p+(s-subst(p,x,x^2))/2))) - p)); Vec(p+O(x*x^n))}

G.f.: x + (1 + P(x))*B(x^2) where P(x) is the g.f. of A339158 and B(x) is the g.f. of A003430.

A202180 Number of n-element unlabeled connected N-free posets.

Original entry on oeis.org

1, 1, 3, 9, 31, 115, 474, 2097, 9967, 50315, 268442, 1505463, 8840306, 54169431

Offset: 1

N. J. A. Sloane, Dec 13 2011

Soheir M. Khamis, Height counting of unlabeled interval and N-free posets, Discrete Math. 275 (2004), no. 1-3, 165-175.

Row sums of A202178 and A202179.

Cf. A003430, A007453, A053554.

Missing term a(12) inserted by Salah Uddin Mohammad, May 26 2020

A339158 Number of essentially parallel achiral series-parallel networks with n elements.

Original entry on oeis.org

1, 1, 2, 4, 8, 18, 37, 84, 180, 413, 902, 2084, 4628, 10726, 24128, 56085, 127421, 296955, 680092, 1588665, 3662439, 8574262, 19875081, 46628789, 108584460, 255264307, 596774173, 1405626896, 3297314994, 7780687159, 18305763571, 43271547808, 102069399803

Offset: 1

Andrew Howroyd, Nov 27 2020

nonn

A series configuration is the unit element or an ordered concatenation of two or more parallel configurations and a parallel configuration is the unit element or a multiset of two or more series configurations. a(n) is the number of parallel configurations with n unit elements that are invariant under the reversal of all contained series configurations.

			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) = 1: (o|o).
a(3) = 2: (o|oo).
a(4) = 4: (o|ooo), (oo|oo), (o|o|oo), (o|o|o|o).
a(5) = 8: (o|oooo), (o|(o|o)(o|o)), (o|o(o|o)o), (oo|ooo), (o|o|ooo), (o|oo|oo), (o|o|o|oo), (o|o|o|o|o).
a(6) = 16 includes (o(o|o)|(o|o)o) which is the first example of a network that is achiral but does not have reflective symmetry when embedded in the plane as shown below (edges correspond to elements):
               A
             /   \\
            o      o   --- No reflective symmetry ---
             \\  /
               Z

Cf. A003430, A007454 (oriented), A339157, A339159, A339224 (unoriented).

\\ here B(n) gives A003430 as a power series.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
B(n)={my(p=x+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+x)))); p}
seq(n)={my(q=subst(B((n+1)\2), x, x^2), s=x^2+q^2/(1+q), p=x+O(x^2)); for(n=1, n\2, my(t=x + q*(1 + p)); p=x + x*Ser(EulerT(Vec(t+(s-subst(t,x,x^2))/2))) - t); Vec(p+O(x*x^n))}

G.f.: x - S(x) - 1 + exp(Sum_{k>=1} (S(x^k) + (R(x^(2*k)) - S(x^(2*k)))/2)/k) where S(x) is the g.f. of A339157 and R(x) is the g.f. of A007453.

A339223 Number of essentially series unoriented series-parallel networks with n elements.

Original entry on oeis.org

1, 1, 2, 6, 17, 57, 196, 723, 2729, 10638, 42161, 169912, 692703, 2853523, 11852644, 49592966, 208800209, 883970867, 3760605627, 16068272965, 68925340187, 296705390322, 1281351319402, 5549911448062, 24103086681839, 104938476264310, 457920147387969, 2002462084788769

Offset: 1

Andrew Howroyd, Nov 27 2020

nonn

See A339225 for additional details.

			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) = 1: (oo), (o|o).
a(3) = 2: (ooo), (o(o|o)).
a(4) = 6: (oooo), (oo(o|o)), (o(o|o)o), ((o|o)(o|o)), (o(o|oo)), (o(o|o|o)).

Cf. A003430, A007453 (oriented), A339157 (achiral), A339224, A339225.

\\ here B(n) gives A003430 as a power series.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
B(n)={my(p=x+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+x)))); p}
seq(n)={my(q=subst(B((n+1)\2), x, x^2), s=x^2+q^2/(1+q), p=x+O(x^2)); for(n=1, n\2, p = x + q*(1 + x + x*Ser(EulerT(Vec(p+(s-subst(p, x, x^2))/2))) - p)); Vec(p+x+subst(x^2/(1+x),x,B(n)))/2}

a(n) = (A007453(n) + A339157(n))/2.

A202181 Triangle read by rows: T(n,k) = number of n-element unlabeled N-free posets of height k (1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 6, 1, 1, 13, 24, 10, 1, 1, 25, 77, 61, 15, 1, 1, 43, 228, 291, 130, 21, 1, 1, 76, 644, 1229, 856, 246, 28, 1, 1, 128, 1776, 4872, 4840, 2136, 427, 36, 1, 1, 216, 4854, 18711, 25107, 15543, 4733, 694, 45, 1, 1, 354, 13184, 70858, 124167, 101538, 43120, 9577, 1071, 55, 1

Offset: 1

N. J. A. Sloane, Dec 13 2011

			Triangle begins:
1
1 1
1 3 1
1 7 6 1
1 13 24 10 1
1 25 77 61 15 1
1 43 228 291 130 21 1
1 76 644 1229 856 246 28 1
1 128 1776 4872 4840 2136 427 36 1
1 216 4854 18711 25107 15543 4733 694 45 1
1 354 13184 70858 124167 101538 43120 9577 1071 55 1
...

Soheir M. Khamis, Height counting of unlabeled interval and N-free posets, Discrete Math. 275 (2004), no. 1-3, 165-175.

Row sums give A202182. Cf. A202178, A003430, A007453, A053554.

A350772 Triangle read by rows: T(n,k) is the number of n-element unlabeled series-parallel posets with k connected components.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 9, 4, 1, 1, 30, 12, 4, 1, 1, 103, 45, 13, 4, 1, 1, 375, 160, 48, 13, 4, 1, 1, 1400, 613, 175, 49, 13, 4, 1, 1, 5380, 2354, 680, 178, 49, 13, 4, 1, 1

Offset: 1

Salah Uddin Mohammad, Jan 14 2022

			Triangle begins:
     1;
     1,    1;
     3,    1,   1;
     9,    4,   1,   1;
    30,   12,   4,   1,  1;
   103,   45,  13,   4,  1,  1;
   375,  160,  48,  13,  4,  1, 1;
  1400,  613, 175,  49, 13,  4, 1, 1;
  5380, 2354, 680, 178, 49, 13, 4, 1, 1;
  ...

Row sums give A003430.
Column 1 is A007453.
Cf. A263864 (all posets), A349488 (disconnected).

A356558 Triangle read by rows: T(n,k), where n, k >= 2, is the number of n-element unlabeled connected series-parallel posets with k ordinal terms that are either the singleton or disconnected posets.

Original entry on oeis.org

1, 2, 1, 5, 3, 1, 16, 9, 4, 1, 52, 31, 14, 5, 1, 188, 108, 52, 20, 6, 1, 690, 402, 193, 80, 27, 7, 1, 2638, 1523, 744, 315, 116, 35, 8, 1, 10272, 5934, 2908, 1261, 483, 161, 44, 9, 1, 40782, 23505, 11580, 5085, 2010, 707, 216, 54, 10, 1

Offset: 2

Salah Uddin Mohammad, Aug 12 2022

If a poset P is obtained by taking the ordinal sum of the posets A and B, then the posets A and B are called the ordinal terms of P.

			Triangle begins:
      1;
      2,     1;
      5,     3,     1;
     16,     9,     4,    1;
     52,    31,    14,    5,    1;
    188,   108,    52,   20,    6,   1;
    690,   402,   193,   80,   27,   7,   1;
   2638,  1523,   744,  315,  116,  35,   8,  1;
  10272,  5934,  2908, 1261,  483, 161,  44,  9,  1;
  40782, 23505, 11580, 5085, 2010, 707, 216, 54, 10, 1;
The connected posets counted in the first three rows of the triangle are shown by using the Hasse diagram as follows:
-------
  o
  |
  o
--------------------------
                  |   o
    o     o   o   |   |
   / \     \ /    |   o
  o   o     o     |   |
                  |   o
----------------------------------------------------------
    o    o o o   o o    |                           |
   /|\    \|/    |X|    |                           |   o
  o o o    o     o o    |     o     o   o     o     |   |
                        |     |      \ /     / \    |   o
    o           o       |     o       o     o   o   |   |
    |          / \      |    / \      |      \ /    |   o
    o   o     o   \     |   o   o     o       o     |   |
     \ /      |    \    |                           |   o
      o       o     o   |                           |

Row sums give A007453.

Cf. A263864 (all posets), A349488 (disconnected).

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

A007454 Number of unlabeled disconnected series-parallel posets with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A339157 Number of essentially series achiral series-parallel networks with n elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A202180 Number of n-element unlabeled connected N-free posets.

Views

Author

Keywords

Links

Crossrefs

Extensions

A339158 Number of essentially parallel achiral series-parallel networks with n elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A339223 Number of essentially series unoriented series-parallel networks with n elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A202181 Triangle read by rows: T(n,k) = number of n-element unlabeled N-free posets of height k (1 <= k <= n).

Views

Author

Keywords

Examples

Links

Crossrefs

A350772 Triangle read by rows: T(n,k) is the number of n-element unlabeled series-parallel posets with k connected components.

Views

Author

Keywords

Examples

Crossrefs

A356558 Triangle read by rows: T(n,k), where n, k >= 2, is the number of n-element unlabeled connected series-parallel posets with k ordinal terms that are either the singleton or disconnected posets.

Views

Author