A054946 -id:A054946 - cp's OEIS frontend

A003030 Number of strongly connected digraphs with n labeled nodes.

1, 1, 18, 1606, 565080, 734774776, 3523091615568, 63519209389664176, 4400410978376102609280, 1190433705317814685295399296, 1270463864957828799318424676767488, 5381067966826255132459611681511359329536, 90765788839403090457244128951307413371883494400

Offset: 1

N. J. A. Sloane

As usual, there can be an edge both from i to j and from j to i.

			a(3) = 18 (the symbol = denotes a pair of parallel edges): 1->2->3->1 (2 such); 1=2->3->1 (6); 1=2=3->1 (6); 1=2=3=1 (1); 1=2=3 (3).

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 428.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 1..58 (first 18 terms from R. W. Robinson)
Nicholas R. Beaton, Walks obeying two-step rules on the square lattice: full, half and quarter planes, arXiv:2010.06955 [math.CO], 2020.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
J. Ostroff, Counting connected digraphs with gradings, Phd. Thesis (2013), Table 1.
R. W. Robinson, Letter to N. J. A. Sloane, 1980

Cf. A035512, A054946 (strongly connected labeled tournaments), A054947.

A003030 := proc(n)
    option remember;
    if n =1 then
        1;
    else
        A054947(n)+add(binomial(n-1,t-1)*procname(t)*A054947(n-t),t=1..n-1) ;
    end if;
end proc:
seq(A003030(n),n=1..10) ; # R. J. Mathar, May 10 2016

b[1]=1; b[n_]:=b[n]=2^(n*(n-1))-Sum[Binomial[n,j]*2^((n-1)*(n-j))*b[j],{j,1,n-1}];
a[1]=1; a[n_]:=a[n]=b[n]+Sum[Binomial[n-1,j-1]*b[n-j]*a[j],{j,1,n-1}];
Table[a[n],{n,1,15}] (* Vaclav Kotesovec, May 19 2015 *)

\\ here B(n) is A054947 as vector.
B(n)={my(v=vector(n)); v[1]=1; for(n=2, #v, v[n]=2^(n*(n-1))-sum(j=1, n-1, binomial(n, j)*2^((n-1)*(n-j))*v[j])); v}
seq(n)={my(u=B(n), v=vector(n)); v[1]=1; for(n=2, #v, v[n]=u[n]+sum(j=1, n-1, binomial(n-1, j-1)*u[n-j]*v[j])); v} \\ Andrew Howroyd, Sep 10 2018

a(n) ~ 2^(n*(n-1)). - Vaclav Kotesovec, May 19 2015

a(12)-a(13) added by Andrew Howroyd, Sep 10 2018

A054947 Enumerates pairs consisting of a strongly connected labeled tournament and an arbitrary labeled tournament.

Original entry on oeis.org

1, 0, 16, 1536, 557056, 731381760, 3517947314176, 63491024068018176, 4399839304395507367936, 1190389701200990489133711360, 1270450770186900638201337522159616, 5381052721259860098970976735257549602816, 90765718885519516263620106778209295628266110976

Offset: 1

N. J. A. Sloane, May 24 2000

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 428, see b_n.

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. A003030, A054946, A006125.

A054947 := proc(n)
    option remember;
    if n = 1 then
        1;
    else
        2^(n*(n-1))-add(binomial(n,t)*2^((n-1)*(n-t))*procname(t),t=1..n-1) ;
    end if;
end proc: # R. J. Mathar, May 10 2016

a[1] = 1; a[n_] := a[n] = 2^(n(n-1)) - Sum[Binomial[n, j] 2^((n-1)(n-j)) a[j], {j, 1, n-1}];
Array[a, 13] (* Jean-François Alcover, Aug 27 2019 *)

seq(n)={my(v=vector(n)); v[1]=1; for(n=2, #v, v[n]=2^(n*(n-1))-sum(j=1, n-1, binomial(n, j)*2^((n-1)*(n-j))*v[j])); v} \\ Andrew Howroyd, Sep 09 2018

a(n) = A054946(n) * A006125(n). - Andrew Howroyd, Jan 10 2022

More terms from Vladeta Jovovic, Mar 11 2003

A051337 Number of strongly connected tournaments on n nodes.

Original entry on oeis.org

1, 1, 0, 1, 1, 6, 35, 353, 6008, 178133, 9355949, 884464590, 152310149735, 48234782263293, 28304491788158056, 30964247546702883729, 63468402142317299907481, 244785748571033855024746438, 1782909084196274276970660380187, 24602074618353524534591008760307017

Offset: 0

Vladeta Jovovic

A tournament is strongly connected (or strong) if there is a directed path between any pair of points.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 127, Eq. (5.2.4);
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 523.

Andrew Howroyd, Table of n, a(n) for n = 0..50
John W. Moon, Topics on tournaments, Holt, Rinehard and Winston (1968)
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 11 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Raphael Yuster, Vector clique decompositions, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (2019), 1221-1238.

Cf. A000568, A054946.

m = 20;
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]}] + Sum[Quotient[v[[i]], 2], {i, 1, Length[v]}];
oddp[v_] := (For[i = 1, i <= Length[v], i++, If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1);
b[n_] := b[n] = (s = 0; Do[If[oddp[p] == 1, s += permcount[p]*2^edges[p]], {p, IntegerPartitions[n]}]; s/n!);
B[x_] = Sum[b[k] x^k, {k, 0, m}];
A[x_] = 2 - 1/B[x];
A[x] + O[x]^m // CoefficientList[#, x]& (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd in A000568 *)

G.f.: = 2 - 1/B(x) where B(x) = g.f. for A000568.

a(0)=1 prepended and a(18)-a(19) from Andrew Howroyd, Sep 10 2018

A339590 Irregular triangle read by rows: T(n,k) (n>=2, k>=1) = number of strong tournaments on n nodes with k descents.

Original entry on oeis.org

0, 1, 1, 1, 6, 10, 6, 1, 1, 13, 56, 123, 158, 123, 56, 13, 1, 1, 22, 172, 717, 1910, 3547, 4791, 4791, 3547, 1910, 717, 172, 22, 1, 1, 33, 402, 2674, 11614, 36293, 86305, 161529, 242890, 297003, 297003, 242890, 161529, 86305, 36293, 11614, 2674, 402, 33, 1

Offset: 2

N. J. A. Sloane, Dec 28 2020

			Triangle begins:
0;
1, 1;
1, 6, 10, 6, 1;
1, 13, 56, 123, 158, 123, 56, 13, 1;
1, 22, 172, 717, 1910, 3547, 4791, 4791, 3547, 1910, 717, 172, 22, 1;
1, 33, 402, 2674, 11614, 36293, 86305, 161529, 242890, 297003, 297003, 242890, 161529, 86305, 36293, 11614, 2674, 402, 33, 1;
...

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020.

Row sums are A054946.

Cf. A057273, A339807.

A354607 Triangular array read by rows: T(n,k) is the number of labeled tournaments on [n] that have exactly k irreducible (strongly connected) components, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 2, 0, 6, 0, 24, 16, 0, 24, 0, 544, 240, 120, 0, 120, 0, 22320, 6608, 2160, 960, 0, 720, 0, 1677488, 315840, 70224, 20160, 8400, 0, 5040, 0, 236522496, 27001984, 3830400, 758016, 201600, 80640, 0, 40320, 0, 64026088576, 4268194560, 366729600, 46448640, 8628480, 2177280, 846720, 0, 362880

Offset: 0

Geoffrey Critzer, Jul 08 2022

			Triangle T(n,k) begins:
  1;
  0,     1;
  0,     0,    2;
  0,     2,    0,    6;
  0,    24,   16,    0,  24;
  0,   544,  240,  120,   0, 120;
  0, 22320, 6608, 2160, 960,   0, 720;
  ...

N. J. A. Sloane, Illustration of first 5 terms
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 11 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Cf. A006125 (row sums), A054946 (column k=1), A000142 (main diagonal).

nn = 10; G[x_] := Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn}]; Table[
Take[(Range[0, nn]! CoefficientList[Series[1/(1 - y (1 - 1/ G[x])), {x, 0, nn}], {x, y}])[[i]], i], {i, 1, nn}]

E.g.f.: 1/(1-y*(1-1/A(x))) where A(x) is the e.g.f. for A006125.

cp's OEIS Frontend

A003030 Number of strongly connected digraphs with n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A054947 Enumerates pairs consisting of a strongly connected labeled tournament and an arbitrary labeled tournament.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A051337 Number of strongly connected tournaments on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A339590 Irregular triangle read by rows: T(n,k) (n>=2, k>=1) = number of strong tournaments on n nodes with k descents.

Views

Author

Keywords

Examples

References

Links

Crossrefs

A354607 Triangular array read by rows: T(n,k) is the number of labeled tournaments on [n] that have exactly k irreducible (strongly connected) components, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula