login
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.
3

%I #10 Jan 18 2022 19:37:05

%S 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,

%T 1,1,28,234,711,853,378,50,1,1,36,402,1733,3175,2487,755,70,1,1,45,

%U 650,3755,9767,11813,6431,1400,95,1,1,55,995,7443,26043,44926,38160,15098,2445,125,1

%N 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.

%C 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.

%F T(n,0) = T(n,n-1) = 1.

%F T(n,1) = binomial(n,2).

%F T(n+2,n) = A002623(n).

%F Sum_{k=1..n-1} k*T(n,k) = A339232(n).

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 3, 1;

%e 1, 6, 7, 1;

%e 1, 10, 23, 13, 1;

%e 1, 15, 59, 69, 22, 1;

%e 1, 21, 124, 249, 172, 34, 1;

%e 1, 28, 234, 711, 853, 378, 50, 1;

%e ...

%e In the following examples elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element is denoted by 'o'.

%e T(4,0) = 1: (o|o|o|o).

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

%e T(4,2) = 7: (oo(o|o)), (o(o|o)o), ((o|o)oo), (o(o|oo)), ((o|oo)o), (oo|oo), (o|ooo).

%e T(4,3) = 1: (oooo).

%e The graph of (oo(o|o)) has 4 edges (elements) and 2 interior vertices as shown below:

%e A---o---o===Z (where === is a double edge).

%o (PARI)

%o 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)}

%o 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)}

%o T(n)={[Vecrev(p)|p<-VertexWeighted(n,y)]}

%o { my(A=T(12)); for(n=1, #A, print(A[n])) }

%Y Row sums are A003430.

%Y Cf. A002623, A339228, A339230, A339232.

%K nonn,tabl

%O 1,5

%A _Andrew Howroyd_, Nov 29 2020