A350754 -id:A350754 - cp's OEIS frontend

A054948 Number of labeled semi-strong digraphs on n nodes.

1, 1, 2, 22, 1688, 573496, 738218192, 3528260038192, 63547436065854848, 4400982906402148836736, 1190477715153930158152163072, 1270476960212865235273469079407872, 5381083212549793228422395071641588743168, 90765858793484859057065439213726376149311958016

Offset: 0

N. J. A. Sloane, May 24 2000

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

A digraph is semi-strong iff the following implication holds for all x,y in [n]: If there is a directed path from x to y then x and y are in the same strongly connected component. - Geoffrey Critzer, Oct 07 2023

Andrew Howroyd, Table of n, a(n) for n = 0..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

The unlabeled version is A350754.

Cf. A003030, A054947, A218393.

a[n_] := a[n] = Module[{A}, A = 1+Sum[a[k]*x^k/k!, {k, 1, n-1}]; n!*SeriesCoefficient[Sum[2^(k^2-k)*x^k/k!/(A /. x -> 2^k*x) , {k, 0, n}], {x, 0, n}]]; a[0]=1; Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Dec 15 2014, after Paul D. Hanna *)

a(n)=local(A=1+sum(k=1,n-1,a(k)*x^k/k!)+x*O(x^n));n!*polcoeff(sum(k=0,n,2^(k^2-k)*x^k/k!/subst(A,x,2^k*x)),n)
for(n=0,10,print1(a(n),", ")) \\ Paul D. Hanna, Oct 27 2012

E.g.f.: 1/(1-B(x)) where B(x) is e.g.f. for A054947. - Vladeta Jovovic, Mar 11 2003
E.g.f. A(x) satisfies: Sum_{n>=0} 2^(n^2-n)*x^n/n! / A(2^n*x) = 1. - Paul D. Hanna, Oct 27 2012
E.g.f.: exp(B(x)) where B(x) is the e.g.f. of A003030. - Andrew Howroyd, Jan 14 2022

More terms from Vladeta Jovovic, Mar 11 2003

Changed offset to 0 and added a(0)=1 by Paul D. Hanna, Oct 27 2012

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

Original entry on oeis.org

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

Washington Bomfim, May 01 2005

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

			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.

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

Row sums are A350754.
Column 1 is A035512.
Cf. A057276, A106237, A106239.

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

Definition clarified by Andrew Howroyd, Jan 14 2022

cp's OEIS Frontend

A054948 Number of labeled semi-strong digraphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions