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

Author

Andrew Howroyd, Nov 29 2020

Keywords

• nonn
• tabl

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.

Examples

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

Crossrefs

Row sums are A003430.

Cf. A002623, A339228, A339230, A339232.

Programs

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

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