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

1, 2, 2, 3, 7, 3, 4, 18, 18, 4, 5, 42, 87, 42, 5, 6, 90, 396, 396, 90, 6, 7, 186, 1677, 3503, 1677, 186, 7, 8, 368, 6877, 28435, 28435, 6877, 368, 8, 9, 710, 27285, 222943, 425803, 222943, 27285, 710, 9, 10, 1334, 105818, 1705337, 6084393, 6084393, 1705337, 105818, 1334, 10

Offset

1,2

Comments

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

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.

This sequence first appears in the field of electronics. In particular, T(n,k) is also the number of (s,p) gates as defined in the Detjens reference.

References

E. Detjens, G. Gannot, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang, "Technology Mapping in MIS", Proc. 1987 IEEE Internat. Conf. Computer-Aided Design, pp. 116-119.

Links

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

M. R. C. M. Berkelaar and J. A. G. Jess, Technology mapping for standard-cell generators, [1988] IEEE International Conference on Computer-Aided Design (ICCAD-89) Digest of Technical Papers, Santa Clara, CA, USA, 1988, pp. 470-473.

Formula

T(n,k) = T(k,n).

T(n,k) = A391485(n,k) + A391485(k,n) - 1.

Example

Array begins:
==============================================================
n\k | 1   2     3       4        5          6            7 ...
----+---------------------------------------------------------
  1 | 1   2     3       4        5          6            7 ...
  2 | 2   7    18      42       90        186          368 ...
  3 | 3  18    87     396     1677       6877        27285 ...
  4 | 4  42   396    3503    28435     222943      1705337 ...
  5 | 5  90  1677   28435   425803    6084393     85307647 ...
  6 | 6 186  6877  222943  6084393  154793519   3854595207 ...
  7 | 7 368 27285 1705337 85307647 3854595207 168237515231 ...
  ...

Prog

(PARI) \\ T(n) gives n diagonals.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
T(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] ));
  vector(n, r, vector(r, k, my(j=r+1-k); M[j, k] + M[k, j] - 1))
}
{ my(A=T(14)); for(i=1, #A\2, for(j=1, #A\2, print1(A[i+j-1][i], ", ")); print) }

Crossrefs

Main diagonal is A007803.

Columns 1..6 are A000027, A037294, A037295, A037296, A037297, A037298.

Cf. A339153, A391485.

Sequence in context: A296019 A134232 A123934 * A363365 A208151 A203362

Adjacent sequences: A391481 A391482 A391483 * A391485 A391486 A391487

Keyword

nonn,tabl

Author

Andrew Howroyd, Dec 16 2025

Status

approved