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

Author

Washington Bomfim, May 01 2005

Keywords

• nonn
• tabl

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

Examples

			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.
		

Links

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

Crossrefs

Row sums are A350754.

Column 1 is A035512.

Cf. A057276, A106237, A106239.

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

Extensions

Definition clarified by Andrew Howroyd, Jan 14 2022