A391485 Array read by antidiagonals: T(n,k) is the number of nonequivalent essentially parallel series-parallel networks with longest path of at most n edges and largest cut set of at most k edges.

1, 2, 1, 3, 4, 1, 4, 12, 7, 1, 5, 32, 44, 11, 1, 6, 75, 254, 143, 16, 1, 7, 165, 1277, 1752, 401, 22, 1, 8, 340, 5846, 18420, 10016, 1032, 29, 1, 9, 674, 24842, 171641, 212902, 51303, 2444, 37, 1, 10, 1289, 100334, 1466235, 3930265, 2154129, 239103, 5485, 46, 1

Offset

1,2

Comments

Equivalence is up to rearrangement of the order of elements in both series and parallel configurations.

Also, T(n,k) is the number of nonequivalent essentially series series-parallel networks with longest path at most k edges and largest cut set of at most n edges.

A series configuration is a multiset of two or more parallel configurations and a parallel configuration is a multiset of two or more series configurations. The unit element is a special case and is considered to be both a series and a parallel configuration.

In a series configuration, the maximum path length equals the sum of the maximum path lengths of the components and the maximum cut size equals the greatest of the maximum cut sizes of the components. In a parallel configuration, the maximum path length equals the greatest of the maximum path lengths of the components and the maximum cut size equals the sum of the maximum cut sizes of the components.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)

Formula

T(n,1) = 1.

T(n,k) = T(n,k-1) + [x^k] 1/Product_{i=1..k-1} (1 - x^i)^(T(i,n) - T(i-1,n)) for k > 1.

Example

Array begins:
===========================================================
n\k | 1  2    3      4        5          6           7 ...
----+-----------------------------------------------------
  1 | 1  2    3      4        5          6           7 ...
  2 | 1  4   12     32       75        165         340 ...
  3 | 1  7   44    254     1277       5846       24842 ...
  4 | 1 11  143   1752    18420     171641     1466235 ...
  5 | 1 16  401  10016   212902    3930265    65715861 ...
  6 | 1 22 1032  51303  2154129   77396760  2497716726 ...
  7 | 1 29 2444 239103 19591787 1356878482 84118757616 ...
   ...
T(n,1) = 1 because the only parallel arrangement with largest cut set equal to 1 is the unit element.
T(1,k) = k because there is one length 1 parallel arrangement consisting of k edges for each k.
In order to compute T(4,3) = 143: take (4,32) from column 4; determine first differences (4,28); then the Euler transform of (4,28,0) gives (4,38,132). Only the 132 is needed, and T(4,3) = T(4,2) + 132 = 11 + 132 = 143.

Prog

(PARI)
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
HalfMtx(n) = { my(M=matrix(n, n)); for(r=1, n, M[r, 1]=1; for(k=1, r-1, my(j=r+1-k); M[k, j] = M[k, j-1] + EulerT(vector(j, i, if(i==j, 0, M[i, k]-if(i>1, M[i-1, k]))))[j] )); M }
{ my(N=7, M=HalfMtx(2*N-1)); for(n=1, N, print(M[n, 1..N])) }

Crossrefs

Columns 1..2 are A000012, A000124.

Row 2 is A391486.

Main diagonal is A391487.

Cf. A391484.

Sequence in context: A327083 A104002 A073135 * A063804 A387934 A213800

Adjacent sequences: A391482 A391483 A391484 * A391486 A391487 A391488

Keyword

nonn,tabl

Author

Andrew Howroyd, Dec 17 2025

Status

approved