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.

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,5

Comments

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.

Links

Table of n, a(n) for n=1..66.

Formula

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

Example

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

Prog

(PARI)
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])) }

Crossrefs

Row sums are A003430.

Cf. A002623, A339228, A339230, A339232.

Sequence in context: A210866 A245474 A338369 * A133713 A008278 A213735

Adjacent sequences: A339228 A339229 A339230 * A339232 A339233 A339234

Keyword

nonn,tabl

Author

Andrew Howroyd, Nov 29 2020

Status

approved