A035512 -id:A035512 - cp's OEIS frontend

A054952 Number of unlabeled semi-strong digraphs on n nodes with pairwise different components.

1, 1, 6, 88, 5136, 1052154, 706474926, 1581054875274, 12140605885784816, 328173091958855376334, 31831409045512513121561226, 11234306828778006073392046869300, 14576263867446651299709243211339018934, 70075728362101598938266196294267261948879446

Offset: 1

N. J. A. Sloane, May 24 2000

Weigh transform of A035512. - Andrew Howroyd, Sep 10 2018

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

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

Cf. A035512, A054951, A054953, A054954.

m = 15;
A035512 = Cases[Import["https://oeis.org/A035512/b035512.txt", "Table"], {, }][[All, 2]];
gf = -1 + Product[(1 + x^n)^A035512[[n + 1]], {n, 1, m}];
CoefficientList[gf + O[x]^m , x] // Rest (* Jean-François Alcover, Aug 26 2019, after Andrew Howroyd *)

G.f.: -1 + Product_{n > 0} (1 + x^n)^A035512(n). - Andrew Howroyd, Sep 10 2018

More terms from Vladeta Jovovic, Mar 11 2003

a(12)-a(14) from Andrew Howroyd, Sep 10 2018

A054953 Number of unlabeled semi-strong digraphs on n nodes with an odd number of pairwise different components.

Original entry on oeis.org

1, 1, 5, 83, 5048, 1047013, 705422455, 1580348377261, 12139024826336632, 328160951350054991463, 31831080872414173375174213, 11234274997368911879051177335450, 14576252633139821208116086572516525403, 70075713785837731364265242597960381223077163

Offset: 1

N. J. A. Sloane, May 24 2000

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

Cf. A054951, A054952, A054954.

m = 15;
A035512 = Cases[Import["https://oeis.org/A035512/b035512.txt", "Table"], {, }][[All, 2]];
gf = -Product[(1 - x^n)^A035512[[n + 1]], {n, 1, m}] + Product[(1 + x^n)^A035512[[n + 1]], {n, 1, m}];
CoefficientList[gf + O[x]^m , x]/2 // Rest (* Jean-François Alcover, Aug 26 2019, after Andrew Howroyd *)

a(n) = (A054952(n) + A054951(n))/2. - Andrew Howroyd, Sep 10 2018

More terms from Vladeta Jovovic, Mar 11 2003

a(12)-a(14) from Andrew Howroyd, Sep 10 2018

A054954 Number of unlabeled semi-strong digraphs on n nodes with an even number of pairwise different components.

Original entry on oeis.org

0, 0, 1, 5, 88, 5141, 1052471, 706498013, 1581059448184, 12140608800384871, 328173098339746387013, 31831409094194340869533850, 11234306830091593156638822493531, 14576263867574000953696306880725802283

Offset: 1

N. J. A. Sloane, May 24 2000

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

Cf. A054951, A054952, A054953.

m = 15;
A035512 = Cases[Import["https://oeis.org/A035512/b035512.txt", "Table"], {, }][[All, 2]];
gf = -2 + Product[(1 - x^n)^A035512[[n + 1]], {n, 1, m}] + Product[(1 + x^n)^A035512[[n + 1]], {n, 1, m}];
CoefficientList[gf + O[x]^m , x]/2 // Rest (* Jean-François Alcover, Aug 26 2019, after Andrew Howroyd *)

a(n) = (A054952(n) - A054951(n))/2. - Andrew Howroyd, Sep 10 2018

More terms from Vladeta Jovovic, Mar 11 2003

a(12)-a(14) from Andrew Howroyd, Sep 10 2018

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

A350753 Triangle read by rows: T(n,k) is the number of unlabeled strongly connected digraphs with n arcs and k vertices, n >= 0, k = 1..n+1.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 1, 4, 1, 0, 0, 0, 1, 16, 7, 1, 0, 0, 0, 0, 22, 58, 10, 1, 0, 0, 0, 0, 22, 240, 165, 14, 1, 0, 0, 0, 0, 11, 565, 1281, 365, 18, 1, 0, 0, 0, 0, 5, 928, 6063, 4838, 733, 23, 1, 0, 0, 0, 0, 1, 1065, 19591, 38516, 14661, 1317, 28, 1, 0

Offset: 0

Andrew Howroyd, Jan 14 2022

			Triangle begins:
  1;
  0, 0;
  0, 1, 0;
  0, 0, 1,  0;
  0, 0, 2,  1,   0;
  0, 0, 1,  4,   1,    0;
  0, 0, 1, 16,   7,    1,   0;
  0, 0, 0, 22,  58,   10,   1,  0;
  0, 0, 0, 22, 240,  165,  14,  1, 0;
  0, 0, 0, 11, 565, 1281, 365, 18, 1, 0;

Row sums are A350752.
Column sums are A035512.
Cf. A057276 (transpose), A350450, A350489.

\\ See PARI link in A350489 for program code.
my(A=A350753rows(10)); for(n=1, #A, print(A[n]))

A361582 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k strongly connected components.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 5, 5, 6, 0, 83, 62, 42, 31, 0, 5048, 2494, 1172, 592, 302, 0, 1047008, 330063, 103961, 38312, 15616, 5984, 0, 705422362, 137934757, 28095923, 7243110, 2297690, 795930, 243668, 0, 1580348371788, 184557780045, 23226116293, 3951426731, 914429926, 261269562, 79512478, 20286025

Offset: 0

Andrew Howroyd, Mar 16 2023

			Triangle begins:
  1;
  0,       1;
  0,       1,      2;
  0,       5,      5,      6;
  0,      83,     62,     42,    31;
  0,    5048,   2494,   1172,   592,   302;
  0, 1047008, 330063, 103961, 38312, 15616, 5984;
  ...

Wikipedia, Strongly connected component.

Column k=1 is A035512.
Main diagonal is A003087.
Row sums are A000273.
The labeled version is A361455.
Cf. A106238, A350794, A361587, A361588.

\\ See PARI link in A350794 for program code.
{ my(A=A361582triang(6)); for(n=1, #A, print(A[n])) }

A361588 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k strongly connected components and without isolated nodes.

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 0, 5, 4, 4, 0, 83, 57, 37, 25, 0, 5048, 2411, 1110, 550, 271, 0, 1047008, 325015, 101467, 37140, 15024, 5682, 0, 705422362, 136887749, 27765860, 7139149, 2259378, 780314, 237684, 0, 1580348371788, 183852357683, 23088181536, 3923330808, 907186816, 258971872, 78716548, 20042357

Offset: 0

Andrew Howroyd, Mar 16 2023

			Triangle begins:
  1;
  0,       0;
  0,       1,      1;
  0,       5,      4,      4;
  0,      83,     57,     37,    25;
  0,    5048,   2411,   1110,   550,   271;
  0, 1047008, 325015, 101467, 37140, 15024, 5682;
  ...

Column k=1 is A035512.
Main diagonal is A361589.
Row sums are A053598.
Cf. A350794, A361582, A361587, A361590.

\\ See PARI link in A350794 for program code.
{ my(A=A361588triang(6)); for(n=1, #A, print(A[n])) }

T(n,k) = A361582(n,k) - A361582(n-1,k-1).

A049387 Number of rooted unlabeled strongly connected digraphs with n nodes.

Original entry on oeis.org

1, 1, 10, 287, 24427, 6222400, 4924590115, 12632686344657, 109225745061589342, 3281390460782419035867, 350135321051253376431022071, 134810599506208376766503740475912, 189491014587142646710566991248361106383, 981059614010249061197621212287544752507380541

Offset: 1

Valery A. Liskovets

nonn

There is a rather difficult formula (simplified in 1973). The subsequent published value 6222928 for n=6 needs to be verified.

The correct value is 6222400. Terms up to a(7) have been confirmed by brute force using digraphs generated by nauty. - Andrew Howroyd, Jan 12 2022

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. A. Liskovets, The number of strongly connected directed graphs, Mat. Notes, 8 (1970), 877-882

Cf. A035512, A350794.

\\ See PARI link in A350794 for program code.
A049387seq(15) \\ Andrew Howroyd, Jan 22 2022

Terms a(6) and beyond from Andrew Howroyd, Jan 12 2022

A350754 Number of semi-strong digraphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 7, 91, 5144, 1052251, 706480081, 1581055927702, 12140606592270147, 328173093539912361767, 31831409057653120420337536, 11234306829106179168513020426663, 14576263867478482708779036941179024765, 70075728362112833245095630646535639894359350

Offset: 0

Andrew Howroyd, Jan 14 2022

nonn

A digraph is semi-strong if all its weakly connected components are strongly connected.

Andrew Howroyd, Table of n, a(n) for n = 0..50

The labeled version is A054948.
Row sums of A106238.
Cf. A035512.

Euler transform of A035512.

A361587 Triangle read by rows: T(n,k) is the number of weakly connected digraphs on n unlabeled nodes with k strongly connected components.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 5, 4, 4, 0, 83, 56, 36, 24, 0, 5048, 2406, 1101, 542, 267, 0, 1047008, 324917, 101307, 37017, 14947, 5647, 0, 705422362, 136882286, 27757789, 7134897, 2257234, 779257, 237317, 0, 1580348371788, 183851281949, 23086772643, 3922864504, 907027520, 258909828, 78691767, 20035307

Offset: 0

Andrew Howroyd, Mar 16 2023

			Triangle begins:
  1;
  0,       1;
  0,       1,      1;
  0,       5,      4,      4;
  0,      83,     56,     36,    24;
  0,    5048,   2406,   1101,   542,   267;
  0, 1047008, 324917, 101307, 37017, 14947, 5647;
  ...

Column k=1 is A035512.
Main diagonal is A101228.
Row sums are A003085.
Cf. A350794, A361582, A361588.

\\ See PARI link in A350794 for program code.
{ my(A=A361587triang(6)); for(n=1, #A, print(A[n])) }

cp's OEIS Frontend

A054952 Number of unlabeled semi-strong digraphs on n nodes with pairwise different components.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A054953 Number of unlabeled semi-strong digraphs on n nodes with an odd number of pairwise different components.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A054954 Number of unlabeled semi-strong digraphs on n nodes with an even number of pairwise different components.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A350753 Triangle read by rows: T(n,k) is the number of unlabeled strongly connected digraphs with n arcs and k vertices, n >= 0, k = 1..n+1.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A361582 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k strongly connected components.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A361588 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k strongly connected components and without isolated nodes.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A049387 Number of rooted unlabeled strongly connected digraphs with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A350754 Number of semi-strong digraphs on n unlabeled nodes.

Views