A003430
Number of unlabeled series-parallel posets (i.e., generated by unions and sums) with n nodes.
Original entry on oeis.org
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
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
-
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
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
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;
...
-
\\ 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]))}
A339159
Number of achiral series-parallel networks with n elements.
Original entry on oeis.org
1, 2, 3, 7, 12, 29, 54, 130, 258, 616, 1274, 3030, 6458, 15287, 33335, 78694, 174587, 411469, 925246, 2179010, 4952389, 11662221, 26733827, 62980863, 145385388, 342766624, 795810810, 1878109984, 4381423357, 10352044123, 24247955489, 57362089607
Offset: 1
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) = 3: (ooo), (o|oo), (o|o|o), (o|ooo), (oo|oo), (o|o|oo), (o|o|o|o).
a(4) = 7: (oooo), ((o|o)(o|o)), (o(o|o)o).
-
\\ 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), t=p); for(n=1, n\2, t=x + q*(1 + p); p=x + x*Ser(EulerT(Vec(t+(s-subst(t,x,x^2))/2))) - t); Vec(p+t-x+O(x*x^n))}
A339224
Number of essentially parallel unoriented series-parallel networks with n elements.
Original entry on oeis.org
1, 1, 2, 5, 13, 41, 132, 470, 1730, 6649, 26122, 104814, 426257, 1754055, 7282630, 30470129, 128304158, 543303752, 2311904374, 9880776407, 42394198909, 182537610058, 788473887942, 3415782381520, 14837307126498, 64608442956047, 281975101347994, 1233237605651194
Offset: 1
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: (o|o|o), (o|oo).
a(4) = 5: (o|o|o|o), (o|o|oo), (oo|oo), (o|ooo), (o|o(o|o)).
-
\\ 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+subst(x/(1+x), x, B(n)))/2}
A339296
Number of unoriented series-parallel networks with n elements and without multiple unit elements in parallel.
Original entry on oeis.org
1, 1, 2, 4, 9, 23, 60, 170, 496, 1505, 4665, 14772, 47415, 154093, 505394, 1671009, 5561274, 18615687, 62624016, 211605003, 717823582, 2443711716, 8345934897, 28587110560, 98181058020, 338029066457, 1166451261583, 4033596172701, 13975467586797, 48509872173875
Offset: 1
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(2) = 1: (oo).
a(3) = 2: (ooo), (o|oo).
a(4) = 4: (oooo), (o(o|oo)), (o|ooo), (oo|oo).
a(5) = 9: (ooooo), (oo(o|oo)), (o(o|oo)o), (o(o|ooo)), (o(oo|oo)), (o|oooo), (o|o(o|oo)), (oo|ooo), (o|oo|oo).
-
\\ here B(n) gives A339290 as a power series.
\\ Note replacing Z by x/(1-x) gives A339225.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
B(n, Z=x)={my(p=Z+O(x^2)); for(n=2, n, p = Z + (1 + Z)*x*Ser(EulerT( Vec(p^2/(1+p), -n) ))); p}
seq(n, Z=x)={my(q=subst(B((n+1)\2, Z), x, x^2), s=q^2/(1+q), p=Z+O(x^2), t=0); forstep(n=2, n, 2, t=q*(1 + p); p=Z + (1 + Z)*x*Ser(EulerT(Vec(t+(s-subst(t, x, x^2))/2, -n-1))) - t); Vec(p+t+B(n,Z))/2}
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
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)).
-
\\ 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}
A339280
Number of unoriented series-parallel networks with n elements of 2 colors.
Original entry on oeis.org
2, 6, 22, 106, 582, 3622, 24060, 167803, 1206852, 8881775, 66496238, 504729590, 3874281594, 30020527274, 234498941338, 1844550287865, 14597849688004, 116151844649673, 928633009522942, 7456338969251761, 60101579662366508, 486145542528043029, 3944844113529346468
Offset: 1
In the following examples, elements in series are juxtaposed and elements in parallel are separated by '|'.
a(1) = 2: (1), (2).
a(2) = 6: (11), (12), (22), (1|1), (1|2), (2|2).
A339283
Number of unoriented series-parallel networks with n integer valued elements spanning an initial interval of positive integers.
Original entry on oeis.org
1, 4, 28, 361, 7061, 184327, 5941855, 226973560, 10011116097, 500553647373, 27975194135702, 1728193768303770, 116934429186262096, 8600448307248025405, 683181845460624644202, 58290243136791332908001, 5316517137637684870655592, 516199318599186277653647746
Offset: 1
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).
-
\\ See A339282 for R(n,k).
seq(n)={sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) )}
A339281
Number of unoriented series-parallel networks with n colored elements using exactly 2 colors.
Original entry on oeis.org
0, 2, 14, 84, 522, 3426, 23404, 165417, 1197934, 8847201, 66359672, 504180138, 3872043674, 30011312118, 234460670790, 1844390161675, 14597175479270, 116148990100435, 928620864502940, 7456287071153017, 60101357023288316, 486144584042042269, 3944839973878931780
Offset: 1
In the following examples elements in series are juxtaposed and elements in parallel are separated by '|'.
a(2) = 2: (12), (1|2).
a(3) = 14: (112), (121), (122), (212), (1(1|2)), (1(2|2)), (2(1|1)), (2(1|2)), (1|12), (1|22), (2|11), (2|12), (1|1|2), (1|2|2).
A339285
Triangle read by rows: T(n,k) is the number of unoriented series-parallel networks whose multigraph has n edges and k interior vertices, 0 <= k < n.
Original entry on oeis.org
1, 1, 1, 1, 2, 1, 1, 4, 5, 1, 1, 6, 14, 8, 1, 1, 9, 34, 39, 14, 1, 1, 12, 68, 132, 94, 20, 1, 1, 16, 126, 370, 447, 202, 30, 1, 1, 20, 212, 887, 1625, 1275, 398, 40, 1, 1, 25, 340, 1911, 4955, 5985, 3284, 730, 55, 1, 1, 30, 515, 3765, 13133, 22608, 19245, 7649, 1266, 70, 1
Offset: 1
Triangle begins:
1;
1, 1;
1, 2, 1;
1, 4, 5, 1;
1, 6, 14, 8, 1;
1, 9, 34, 39, 14, 1;
1, 12, 68, 132, 94, 20, 1;
1, 16, 126, 370, 447, 202, 30, 1;
1, 20, 212, 887, 1625, 1275, 398, 40, 1;
1, 25, 340, 1911, 4955, 5985, 3284, 730, 55, 1;
...
T(4,0) = 1: (o|o|o|o).
T(4,1) = 4: ((o|o)(o|o)), (o(o|o|o)), (o|o|oo), (o|o(o|o)).
T(4,2) = 5: (oo(o|o)), (o(o|o)o), (o(o|oo)), (oo|oo), (o|ooo).
T(4,3) = 1: (oooo).
-
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)}
SubPwr(p,e)={my(vars=variables(p)); substvec(p, vars, [v^e|v<-vars])}
BW(n, Z, W)={my(p=Z+O(x^2)); for(n=2, n, p=x*Ser(EulerMT(Vec(W*p^2/(1+W*p)+Z)))); p}
VertexWeighted(n, Z, W)={my(q=SubPwr(BW((n+1)\2, Z, W), 2), W2=SubPwr(W, 2), s=SubPwr(Z, 2)+W2*q^2/(1+W2*q), p=Z+O(x^2), t=p); for(n=1, n\2, t=Z + q*(W + W2*p); p=Z + x*Ser(EulerMT(Vec(t+(s-SubPwr(t, 2))/2))) - t); Vec(p+t-Z+BW(n, Z, W))/2}
T(n)={[Vecrev(p)|p<-VertexWeighted(n, x, y)]}
{ my(A=T(12)); for(n=1, #A, print(A[n])) }
Showing 1-10 of 13 results.
Comments