A000595 -id:A000595 - cp's OEIS frontend

A326216 Number of labeled n-vertex digraphs (without loops) not containing a (directed) Hamiltonian path.

1, 1, 1, 16, 772

Offset: 0

Gus Wiseman, Jun 15 2019

A path is Hamiltonian if it passes through every vertex exactly once.

			The a(3) = 16 edge-sets:
  {}  {12}  {12,13}
      {13}  {12,21}
      {21}  {12,32}
      {23}  {13,23}
      {31}  {13,31}
      {32}  {21,23}
            {21,31}
            {23,32}
            {31,32}

Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Unlabeled digraphs not containing a Hamiltonian path are A326224.
The undirected case is A326205.
The unlabeled undirected case is A283420.
The case with loops is A326213.
Digraphs (without loops) containing a Hamiltonian path are A326217.
Digraphs (without loops) not containing a Hamiltonian cycle are A326218.
Cf. A000595, A002416, A003024, A003216, A057864, A326206, A326214, A326220, A326221, A326225.

Table[Length[Select[Subsets[Select[Tuples[Range[n],2],UnsameQ@@#&]],FindHamiltonianPath[Graph[Range[n],DirectedEdge@@@#]]=={}&]],{n,4}] (* Mathematica 10.2+ *)

A053763(n) = a(n) + A326217(n).

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

A001374 Number of relational systems on n nodes. Also number of directed 3-multigraphs with loops on n nodes.

Original entry on oeis.org

4, 136, 44224, 179228736, 9383939974144, 6558936236286040064, 62879572771326489528942592, 8439543710699844562674685252214784, 16110027001555070629022725866559372785352704, 442829046878106126159584032189649757399796014050181120

Offset: 1

N. J. A. Sloane

W. Oberschelp, "Strukturzahlen in endlichen Relationssystemen", in Contributions to Mathematical Logic (Proceedings 1966 Hanover Colloquium), pp. 199-213, North-Holland Publ., Amsterdam, 1968.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..40
W. Oberschelp, Strukturzahlen in endlichen Relationssystemen, in Contributions to Mathematical Logic (Proceedings 1966 Hanover Colloquium), pp. 199-213, North-Holland Publ., Amsterdam, 1968. [Annotated scanned copy]

Cf. A000595, A004105, A053468, A053516.

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[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
a[n_] := (s=0; Do[s += permcount[p]*4^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Array[a, 15] (* Jean-François Alcover, Jul 08 2018, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i])}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*4^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A001374(n): return int(sum(Fraction(1<<((sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))<<1)+sum(q*r**2 for q, r in p.items())<<1),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 10 2024

More terms from Vladeta Jovovic, Jan 14 2000

A053516 Number of directed 4-multigraphs with loops on n nodes.

Original entry on oeis.org

5, 325, 327125, 6360324375, 2483590604688125, 20211024423069510171875, 3524517841661451239027963515625, 13444967478414031326768049544880110156250, 1139744010069698074379093986222808985702884783203125

Offset: 1

Vladeta Jovovic, Jan 14 2000

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

Cf. A000595, A004105, A001374.

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[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
a[n_] := (s=0; Do[s += permcount[p]*5^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Array[a, 15] (* Jean-François Alcover, Jul 08 2018, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i])}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*5^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

a(9) from Andrew Howroyd, Oct 22 2017

A308111 Isomorphism classes of Eulerian digraphs with n vertices, allowing loops.

Original entry on oeis.org

1, 2, 6, 24, 160, 2512, 129816, 22665792, 13056562208, 24953006054144, 160860329639968800, 3555065836569542246400, 273147301191314006316868352, 73832333258502021627712839197696, 70920540648597652305602460997787710080, 244186544390677638132290202415190606165938176, 3036252267734950687777830287721323374283100639476736

Offset: 0

Brendan McKay, May 11 2019

Eulerian means that for every vertex the in-degree equals the out-degree.

			For n=2 the a(2)=6 solutions are: two non-adjacent vertices with or without loops (3 cases), two vertices with or without loops connected by edges in each direction (3 cases).

Gus Wiseman, Non-isomorphic representatives of the a(3) = 24 Eulerian digraphs with loops.

For labeled digraphs rather than isomorphism classes see A229865.
For isomorphism classes with loops forbidden see A058338.
Cf. A308128 (connected version of this).
Cf. A000273, A000595, A002416, A002720, A308161.

Euler transform of A308128.

Terms a(10) and beyond from Andrew Howroyd, Apr 12 2020

A001377 Number of relations with 4 arguments on n nodes.

Original entry on oeis.org

2, 32896, 402975273205975947935744, 4824670384888174809315457708695329515706856139873561594988392833332671414272

Offset: 1

N. J. A. Sloane

W. Oberschelp, "Strukturzahlen in endlichen Relationssystemen", in Contributions to Mathematical Logic (Proceedings 1966 Hanover Colloquium), pp. 199-213, North-Holland Publ., Amsterdam, 1968.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..7
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
W. Oberschelp, Strukturzahlen in endlichen Relationssystemen, in Contributions to Mathematical Logic (Proceedings 1966 Hanover Colloquium), pp. 199-213, North-Holland Publ., Amsterdam, 1968. [Annotated scanned copy]

Cf. A000595, A000662, A051241.

from itertools import product
from math import factorial, prod, lcm
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A001377(n): return int(sum(Fraction(1<Chai Wah Wu, Jul 02 2024

More terms from Vladeta Jovovic

A002500 Number of self-converse relations on n points.

Original entry on oeis.org

1, 2, 8, 44, 436, 7176, 222368, 12376880, 1302871456, 254079924896, 94287450368768, 65986000800656832, 88430997899765949952, 226039101814259861321856, 1112311767839787173832758784

Offset: 0

N. J. A. Sloane

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 155, Table 6.6.1.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Sean A. Irvine, Table of n, a(n) for n = 0..50
F. Harary and E. M. Palmer, Enumeration of self-converse digraphs, Mathematika, 13 (1966), 151-157.

Equals A029849*2 - A000595. Cf. A002499.

In the Encyclopedia of Integer Sequences the n=6 term is given incorrectly as 484256.

Corrected and extended with formula by Christian G. Bower, Jun 15 1998

A051241 Number of relations with 5 arguments on n nodes.

Original entry on oeis.org

2, 2147516416, 2355796086371179106111063334323891357095101187404796307182832141733986304

Offset: 1

Vladeta Jovovic

Alois P. Heinz, Table of n, a(n) for n = 1..5

Cf. A000595, A000662, A001377.

from itertools import product
from math import factorial, prod, lcm
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A051241(n): return int(sum(Fraction(1<Chai Wah Wu, Jul 02 2024

A054919 Number of nonisomorphic connected unlabeled binary relations on n nodes.

Original entry on oeis.org

1, 2, 7, 86, 2818, 285382, 96324549, 112087100482, 458071928280897, 6665704296529088252, 349377209492194571020053, 66602723163954144515240479674, 46557323273646194397778583902876038, 120168498151800396724425973133360413846262, 1152049915423012273792614840793828654424980146983

Offset: 0

N. J. A. Sloane, May 24 2000

			Nonisomorphic connected relations on set {1,2} are {2r1}, {1r1,2r1}, {2r1,2r2}, {1r1,2r1,2r2}, {1r2,2r1}, {1r1,1r2,2r1}, {1r1,1r2,2r1,2r2} so a(2)=7.

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.

Cf. A000595.

nn=7; c=Join[{1,2}, Table[CycleIndex[Join[PairGroup[SymmetricGroup[n],Ordered], Permutations[Range[n^2-n+1,n^2]],2],s] /. Table[s[i]->2, {i,1,n^2-n}], {n,2,nn}]]; f[x_]:=Sum[a[n]x^n,{n,0,nn}]; b=Sum[c[[n+1]]x^n, {n,0,nn}]; sol=SolveAlways[b==Normal[Series[Product[1/(1-x^i)^a[i], {i,1,nn}], {x,0,nn}]], x]; Table[a[n], {n,1,nn}]/.sol (* Geoffrey Critzer, Mar 31 2013 *)

Inverse Euler transform of A000595.

More terms from Vladeta Jovovic, Jul 16 2000

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

A329874 Array read by antidiagonals: A(n,k) = number of digraphs on n unlabeled nodes, arbitrarily colored with k given colors (n >= 1, k >= 1).

Original entry on oeis.org

1, 2, 3, 3, 10, 16, 4, 21, 104, 218, 5, 36, 328, 3044, 9608, 6, 55, 752, 14814, 291968, 1540944, 7, 78, 1440, 45960, 2183400, 96928992, 882033440, 8, 105, 2456, 111010, 9133760, 1098209328, 112282908928, 1793359192848

Offset: 1

Peter Dolland, Nov 23 2019

The coloring of nodes is unrestricted. There is no constraint that all of the k colors have to be used. Nodes with different colors are counted as distinct, nodes with the same color are not. For digraphs with a fixed color set see A329546.

			First six rows and columns:
      1        2          3          4           5           6
      3       10         21         36          55          78
     16      104        328        752        1440        2456
    218     3044      14814      45960      111010      228588
   9608   291968    2183400    9133760    27755016    68869824
1540944 96928992 1098209328 6154473664 23441457680 69924880288
...
n=4, k=3 with A329546:
A(4,3) = 3*218 + 3*2608 + 6336 = 14814.

Cf. A000273 digraphs with one color, A000595 binary relations, A329546 digraphs with exactly k colors, A328773 digraphs with a given color scheme.

\\ here C(p) computes A328773 sequence value for given partition.
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i], v[j]))) + sum(i=1, #v, v[i]-1)}
C(p)={((i, v)->if(i>#p, 2^edges(v), my(s=0); forpart(q=p[i], s+=permcount(q)*self()(i+1, concat(v, Vec(q)))); s/p[i]!))(1, [])}
\\ here mulp(v) computes the multiplicity of the given partition. (see A072811)
mulp(v) = {my(p=(#v)!, k=1); for(i=2, #v, k=if(v[i]==v[i-1], k+1, p/=k!; 1)); p/k!}
wC(p)=mulp(p)*C(p)
A329546(n)={[vecsum(apply(wC, vecsort([Vecrev(p) | p<-partitions(n),#p==m], , 4))) | m<-[1..n]]}
Row(n)=vector(6, k, binomial(k)[2..min(k,n)+1]*A329546(n)[1..min(k,n)]~)
{ for(n=0, 6, print(Row(n))) }

A(1,k) = k.
A(2,k) = k*(2*k+1).
A(n,1) = A000273(n).
A(n,2) = A000595(n).
A(n,4) = A353996(n+1). - Brendan McKay, May 13 2022
A(n,k) = Sum_{i=1..min(n,k)} binomial(k,i)*A329546(n,i).

cp's OEIS Frontend

A326216 Number of labeled n-vertex digraphs (without loops) not containing a (directed) Hamiltonian path.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A001374 Number of relational systems on n nodes. Also number of directed 3-multigraphs with loops on n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A053516 Number of directed 4-multigraphs with loops on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A308111 Isomorphism classes of Eulerian digraphs with n vertices, allowing loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A001377 Number of relations with 4 arguments on n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Extensions

A002500 Number of self-converse relations on n points.

Views

Author

Keywords

References

Links

Formula

Extensions

A051241 Number of relations with 5 arguments on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A054919 Number of nonisomorphic connected unlabeled binary relations on n nodes.