A106238 Triangle read by rows: T(n,m) is the number of semi-strong digraphs on n unlabeled nodes with m connected components.

1, 1, 1, 5, 1, 1, 83, 6, 1, 1, 5048, 88, 6, 1, 1, 1047008, 5146, 89, 6, 1, 1, 705422362, 1052471, 5151, 89, 6, 1, 1, 1580348371788, 706498096, 1052569, 5152, 89, 6, 1, 1, 12139024825260556, 1581059448174, 706503594, 1052574, 5152, 89, 6, 1, 1

Offset

1,4

Comments

The formula T(n,m) is the sum over the partitions of n with m parts 1K1 + 2K2 + ... + nKn, of Product_{i=1..n} binomial(f(i) + Ki - 1, Ki) can be used to count unlabeled graphs of order n with m components if f(i) is the number of non-isomorphic connected components of order i. (In general, f denotes a sequence that counts unlabeled connected combinatorial objects.)

A digraph is semi-strong if all its weakly connected components are strongly connected. - Andrew Howroyd, Jan 14 2022

Links

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

Formula

G.f.: 1/Product_{i>=1} (1-y*x^i)^A035512(i). - Vladeta Jovovic, May 04 2005

Triangle read by rows: T(n, m) is the sum over the partitions of n with m parts 1K1 + 2K2 + ... + nKn, of Product_{i=1..n} binomial(A035512(i) + Ki - 1, Ki).

Example

Triangle begins:
          1;
          1,       1;
          5,       1,    1;
         83,       6,    1,  1;
       5048,      88,    6,  1, 1;
    1047008,    5146,   89,  6, 1, 1;
  705422362, 1052471, 5151, 89, 6, 1, 1;
  ...
T(4,2) = 6 because there are 6 digraphs of order 4 with 2 strongly connected components.

Crossrefs

Row sums are A350754.

Column 1 is A035512.

Cf. A057276, A106237, A106239.

Sequence in context: A246051 A111820 A174912 * A173475 A174919 A156952

Adjacent sequences: A106235 A106236 A106237 * A106239 A106240 A106241

Keyword

nonn,tabl

Author

Washington Bomfim, May 01 2005

Extensions

Definition clarified by Andrew Howroyd, Jan 14 2022

Status

approved