A003087 -id:A003087 - cp's OEIS frontend

A326223 Number of non-Hamiltonian unlabeled n-vertex digraphs (with loops).

1, 0, 7, 80, 2186

Offset: 0

Gus Wiseman, Jun 15 2019

A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.

			Non-isomorphic representatives of the a(2) = 7 digraph edge-sets:
  {}
  {11}
  {12}
  {11,12}
  {11,21}
  {11,22}
  {11,12,22}

Gus Wiseman, Non-isomorphic representatives of the a(3) = 80 non-Hamiltonian digraphs.

The labeled case is A326220.
The case without loops is A326222.
The undirected case is A246446 (without loops) or A326239 (with loops).
Hamiltonian unlabeled digraphs are A326226.
Unlabeled digraphs not containing a Hamiltonian path are A326224.
Cf. A000595, A002416, A003087, A003216, A283420, A326204, A326218, A326225.

A345258 Number of acyclic digraphs (or DAGs) on n unlabeled vertices with one source and one sink.

Original entry on oeis.org

1, 1, 2, 10, 98, 1960, 80176, 6686760, 1129588960, 384610774696, 263104175114712, 360908867732030980, 991603865814038728388, 5453395569997436383751204, 60010050181461052836515513108, 1321051495313052133670927704328040, 58170762510305449187073353930875222256

Offset: 1

Max Alekseyev, Jun 12 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50 (terms 1..40 from Mikhail Tikhomirov)
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.

Row sums of A350491.
The labeled version is A165950.
Cf. A003087, A049531, A122078, A350415, A350492.

A345258seq(16) \\ See PARI link in A122078 for program code.

a(9) from Brendan McKay.

Terms a(10) and beyond from Mikhail Tikhomirov, Jun 16 2021

A101228 Number of weakly connected acyclic digraphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 4, 24, 267, 5647, 237317, 20035307, 3404385285, 1162502511721, 796392234736238, 1093228137893084112, 3004752537725051647790, 16527844667281561960220731, 181891583847006693859132403681, 4004313473818592854334088690859030

Offset: 1

Vladeta Jovovic, Jan 22 2005

nonn

The multiset transformation gives the number acyclic digraphs on n unlabeled nodes with k components:
;
, 1 ;
, 1 , 1 ;
, 5 , 1 , 1 ;
, 28 , 5 , 1 , 1 ;
, 301 , 29 , 5 , 1 , 1 ;
237317 , 6010 , 305 , 29 , 5 , 1 , 1 ; R. J. Mathar, Mar 21 2019

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

Row sums of A350449.
Column sums of A350450.
Cf. A003087 (Euler trans.), A082402, A350451.

A326222 Number of non-Hamiltonian unlabeled n-vertex digraphs (without loops).

Original entry on oeis.org

1, 0, 2, 12, 157, 5883, 696803, 255954536

Offset: 0

Gus Wiseman, Jun 15 2019

A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.

Gus Wiseman, Non-isomorphic representatives of the a(3) = 12 non-Hamiltonian digraphs.

The labeled case is A326218 (without loops) or A326220 (with loops).
The undirected case (without loops) is A246446.
The case with loops is A326223.
Hamiltonian unlabeled digraphs are A326225 (without loops) or A003216 (with loops).
Cf. A000273, A000595, A002416, A003087, A053763, A326216, A326217, A326224, A326226.

a(n) = A000273(n) - A326225(n). - Pontus von Brömssen, Mar 17 2024

a(5)-a(7) (using A000273 and A326225) from Pontus von Brömssen, Mar 17 2024

A350447 Triangle read by rows: T(n,k) is the number of acyclic digraphs on n unlabeled nodes with k arcs, n >=0, k = 0..(n-1)*n/2.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 9, 9, 6, 1, 1, 1, 4, 12, 37, 60, 80, 63, 33, 10, 1, 1, 1, 4, 13, 51, 163, 407, 796, 1169, 1291, 1057, 649, 281, 85, 15, 1, 1, 1, 4, 13, 54, 215, 846, 2690, 7253, 15703, 27596, 39057, 44902, 41723, 31336, 18844, 8983, 3325, 920, 180, 21, 1

Offset: 0

Andrew Howroyd, Dec 31 2021

			Triangle begins:
  [0] 1;
  [1] 1;
  [2] 1, 1;
  [3] 1, 1, 3,  1;
  [4] 1, 1, 4,  9,  9,  6,  1;
  [5] 1, 1, 4, 12, 37, 60, 80, 63, 33, 10, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1350 (rows 0..20)

The labeled version is A081064.
Row sums are A003087.
Cf. A122078, A350449.

\\ See PARI link in A122078 for program code.
{ my(T=AcyclicDigraphsByArcs(6)); for(n=1, #T, print(T[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])) }

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

Original entry on oeis.org

1, 0, 1, 1, 0, 2, 5, 5, 0, 6, 90, 55, 42, 0, 31, 5289, 2451, 974, 592, 0, 302, 1071691, 323709, 94332, 29612, 15616, 0, 5984, 712342075, 135208025, 25734232, 6059018, 1650492, 795930, 0, 243668, 1585944117738, 181427072519, 21650983294, 3358042412, 704602272, 174576110, 79512478, 0, 20286025

Offset: 0

Andrew Howroyd, Mar 16 2023

			Triangle begins:
        1;
        0,      1;
        1,      0,     2;
        5,      5,     0,     6;
       90,     55,    42,     0,    31;
     5289,   2451,   974,   592,     0, 302;
  1071691, 323709, 94332, 29612, 15616,   0, 5984;
  ...

Column k=0 is A361586.
Main diagonal is A003087.
Row sums are A000273.
The labeled version is A361592.
Cf. A350794, A361582, A361588.

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

A361718 Triangular array read by rows. T(n,k) is the number of labeled directed acyclic graphs on [n] with exactly k nodes of indegree 0.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 15, 9, 1, 0, 316, 198, 28, 1, 0, 16885, 10710, 1610, 75, 1, 0, 2174586, 1384335, 211820, 10575, 186, 1, 0, 654313415, 416990763, 64144675, 3268125, 61845, 441, 1, 0, 450179768312, 286992935964, 44218682312, 2266772550, 43832264, 336924, 1016, 1

Offset: 0

Geoffrey Critzer, Apr 02 2023

Also the number of sets of n nonempty subsets of {1..n}, k of which are singletons, such that there is only one way to choose a different element from each. For example, row n = 3 counts the following set-systems:
  {{1},{1,2},{1,3}}    {{1},{2},{1,3}}    {{1},{2},{3}}
  {{1},{1,2},{2,3}}    {{1},{2},{2,3}}
  {{1},{1,3},{2,3}}    {{1},{3},{1,2}}
  {{2},{1,2},{1,3}}    {{1},{3},{2,3}}
  {{2},{1,2},{2,3}}    {{2},{3},{1,2}}
  {{2},{1,3},{2,3}}    {{2},{3},{1,3}}
  {{3},{1,2},{1,3}}    {{1},{2},{1,2,3}}
  {{3},{1,2},{2,3}}    {{1},{3},{1,2,3}}
  {{3},{1,3},{2,3}}    {{2},{3},{1,2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{1,3},{1,2,3}}
  {{2},{1,2},{1,2,3}}
  {{2},{2,3},{1,2,3}}
  {{3},{1,3},{1,2,3}}
  {{3},{2,3},{1,2,3}}

			Triangle begins:
  1;
  0,     1;
  0,     2,     1;
  0,    15,     9,    1;
  0,   316,   198,   28,  1;
  0, 16885, 10710, 1610, 75, 1;
  ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

Cf. A058876 (mirror), A361579, A224069.
Row-sums are A003024, unlabeled A003087.
Column k = 1 is A003025(n) = |n*A134531(n)|.
Column k = n-1 is A058877.
For fixed sinks we get A368602.
A058891 counts set-systems, unlabeled A000612.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A000169, A059201, A082402, A088957, A133686, A334282, A350415, A367904, A367908, A368600, A368601.

nn = 8; B[n_] := n! 2^Binomial[n, 2] ;ggf[egf_] := Normal[Series[egf, {z, 0, nn}]] /. Table[z^i -> z^i/2^Binomial[i, 2], {i, 0, nn}];Table[Take[(Table[B[n], {n, 0, nn}] CoefficientList[ Series[ggf[Exp[(u - 1) z]]/ggf[Exp[-z]], {z, 0, nn}], {z, u}])[[i]], i], {i, 1, nn + 1}] // Grid
nv=4;Table[Length[Select[Subsets[Subsets[Range[n]],{n}], Count[#,{_}]==k&&Length[Select[Tuples[#], UnsameQ@@#&]]==1&]],{n,0,nv},{k,0,n}]

T(n,k) = A368602(n,k) * binomial(n,k). - Gus Wiseman, Jan 03 2024

A087614 Number of unlabeled acyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Original entry on oeis.org

1, 3, 15, 192, 7117

Offset: 1

Detlef Pauly (dettodet(AT)yahoo.de), Sep 12 2003

Jobst Heitzig, Social Choice Under Incomplete, Cyclic Preferences, arXiv:math/0201285 [math.CO], 2002.

Cf. A087613 for the labeled analog, A003087, A087616.

A087616 Number of unlabeled cyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Original entry on oeis.org

0, 0, 1, 26, 2491

Offset: 1

Detlef Pauly (dettodet(AT)yahoo.de), Sep 12 2003

Jobst Heitzig, Social Choice Under Incomplete, Cyclic Preferences, arXiv:math/0201285 [math.CO], 2002.

Cf. A087615 for the labeled analog, A003087, A087614, A000273.

Equals A000273 - A087614.

cp's OEIS Frontend

A326223 Number of non-Hamiltonian unlabeled n-vertex digraphs (with loops).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A345258 Number of acyclic digraphs (or DAGs) on n unlabeled vertices with one source and one sink.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A101228 Number of weakly connected acyclic digraphs on n unlabeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

A326222 Number of non-Hamiltonian unlabeled n-vertex digraphs (without loops).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A350447 Triangle read by rows: T(n,k) is the number of acyclic digraphs on n unlabeled nodes with k arcs, n >=0, k = 0..(n-1)*n/2.

Views

Author

Keywords

Examples

Links

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

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

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A361718 Triangular array read by rows. T(n,k) is the number of labeled directed acyclic graphs on [n] with exactly k nodes of indegree 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A087614 Number of unlabeled acyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Views

Author

Keywords

Links

Crossrefs

A087616 Number of unlabeled cyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Views

Author