A003430 -id:A003430 - cp's OEIS frontend

A339154 Number of essentially series oriented series-parallel networks with n elements and without unit elements in parallel.

0, 1, 1, 1, 3, 6, 14, 30, 70, 165, 397, 961, 2368, 5875, 14722, 37134, 94312, 240823, 618147, 1593606, 4125218, 10717064, 27934867, 73032798, 191464677, 503218042, 1325678981, 3499913710, 9258627528, 24538328431, 65147600774, 173243773337, 461400769439

Offset: 1

Andrew Howroyd, Nov 26 2020

nonn

A series configuration is 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.

			In the following examples, elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element is denoted by 'o'.
a(2) = 1: (oo).
a(3) = 1: (ooo).
a(4) = 1: (oooo).
a(5) = 3: (ooooo), (o(oo|oo)), ((oo|oo)o).
a(6) = 6: (oooooo), (oo(oo|oo)), (o(oo|oo)o), ((oo|oo)oo), (o(oo|ooo)), ((oo|ooo)o).

Cf. A003430, A339151, A339155, A339156.

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

G.f.: P(x)^2/(1 - P(x)) where P(x) is the g.f. of A339155.

G.f.: B(x)^2/(1 + B(x)) where B(x) is the g.f. of A339156.

A339155 Number of essentially parallel oriented series-parallel networks with n elements and without unit elements in parallel.

Original entry on oeis.org

1, 0, 0, 1, 1, 3, 5, 13, 29, 70, 165, 409, 1001, 2505, 6278, 15904, 40447, 103567, 266229, 687668, 1782573, 4637731, 12103112, 31679212, 83135973, 218713492, 576683119, 1523740365, 4033915677, 10698680606, 28422818782, 75629586540, 201539697208, 537818080714

Offset: 1

Andrew Howroyd, Nov 26 2020

nonn

A series configuration is 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.

			In the following examples, elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element is denoted by 'o'.
a(1) = 1: (o).
a(4) = 1: (oo|oo).
a(5) = 1: (oo|ooo).
a(6) = 3: (oo|oooo), (ooo|ooo), (oo|oo|oo).
a(7) = 4: (oo|ooooo), (oo|o(oo|oo)), (oo|(oo|oo)o), (ooo|oooo), (oo|oo|ooo).

Cf. A003430, A339152, A339154, A339156.

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+x*Ser(EulerT(Vec(p^2/(1+p), -n)))); Vec(1 - 1/(1+p))}

G.f.: B(x)/(1 + B(x)) where B(x) is the g.f. of A339156.

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.

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

A301871 Number of N- and bowtie-free posets with n elements.

Original entry on oeis.org

1, 2, 5, 14, 40, 121, 373, 1184, 3823, 12554, 41733, 140301, 475934, 1627440, 5602983, 19406703, 67574371, 236409625, 830582851, 2929246932, 10366380583, 36801225872, 131021870786, 467701875135, 1673584553886, 6002046468815, 21570135722058, 77668429499325, 280167079428684, 1012323004985313

Offset: 1

Stephan Wagner, Mar 28 2018

The number of n-element posets that do not include the two 4-element posets "N" and "bowtie" as induced subposets.

Stephan Wagner, Table of n, a(n) for n = 1..100
T. Hasebe and S. Tsujie, Order quasisymmetric functions distinguish rooted trees, arXiv:1610.03908 [math.CO], 2016-2017.
T. Hasebe and S. Tsujie, Order quasisymmetric functions distinguish rooted trees, Journal of Algebraic Combinatorics 46 (2017), 499-515.
V. Razanajatovo Misanantenaina and S. Wagner, A Tutte-like polynomial for rooted trees and specific posets, arXiv:1803.09623 [math.CO], 2018.

Cf. A000112, A003430, A079144, A079146 for related sequences regarding the enumeration of unlabeled posets.

V=1;Do[V = Normal[Series[(1 - x) Exp[Sum[(2 x^m - x^(2 m)) (V /. x -> x^m)/m, {m, 1, n}]], {x, 0, n}]], {n, 1, 20}]; Table[Coefficient[V,x,n],{n, 1, 20}]

G.f. V(x) = 1 + x + 2x + 5x^2 + ... satisfies V(x) = (1-x)exp[sum_{m >=1} (2x^m-x^(2m))V(x^m)/m] (see Razanajatovo Misanantenaina/Wagner).

A339232 Total number of interior vertices in the multigraphs of all oriented series-parallel networks with n edges.

Original entry on oeis.org

0, 1, 5, 23, 99, 433, 1880, 8238, 36202, 159898, 708517, 3150128, 14042620, 62751693, 280997846, 1260635337, 5664870696, 25493707908, 114882350739, 518318733052, 2341079272919, 10584488664085, 47898510357544, 216940538748652, 983326680302665, 4460343301915203

Offset: 1

Andrew Howroyd, Nov 29 2020

nonn

See A339231 for additional details.

Cf. A003430, A339231.

\\ See A339231 for VertexWeighted.
seq(n)={subst(deriv(VertexWeighted(n,y)), y, 1)}

a(n) = Sum_{k=1..n-1} k*A339231(n,k).

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.

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

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

cp's OEIS Frontend

A339154 Number of essentially series oriented series-parallel networks with n elements and without unit elements in parallel.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A339155 Number of essentially parallel oriented series-parallel networks with n elements and without unit elements in parallel.

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

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

A301871 Number of N- and bowtie-free posets with n elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A339232 Total number of interior vertices in the multigraphs of all oriented series-parallel networks with n edges.

Views

Author

Keywords

Comments

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

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

Views

Author