A000595 -id:A000595 - cp's OEIS frontend

A004105 Number of point-self-dual nets with 2n nodes. Also number of directed 2-multigraphs with loops on n nodes.

1, 3, 45, 3411, 1809459, 7071729867, 208517974495911, 47481903377454219975, 85161307642554753639601848, 1221965550839348597865127102714827, 142024245093355901785105779901319683262778, 135056692539998733060710198802224149631056479068139

Offset: 0

N. J. A. Sloane

A 2-multigraph is similar to an ordinary graph except there are 0, 1 or 2 edges between any two nodes (self-loops are not allowed).

Also nonisomorphic relations on 3-state logic.

F. Harary and R. W. Robinson, Exposition of the enumeration of point-line-signed graphs, pp. 19 - 33 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson and Alois P. Heinz, Table of n, a(n) for n = 0..40 (terms n = 1..13 from R. W. Robinson)
Frank Harary, Edgar M. Palmer, Robert W. Robinson, Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout

Cf. A000595, A001374, A053467, A053516.

Prepend[Table[CycleIndex[Join[PairGroup[SymmetricGroup[n],Ordered], Permutations[Range[n^2-n+1,n^2]],2],s]/.Table[s[i]->3,{i,1,n^2-n}],{n,2,7}],1] (* Geoffrey Critzer, Oct 20 2012 *)
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]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Array[a, 15, 0] (* 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)*3^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 A004105(n): return int(sum(Fraction(3**((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())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 10 2024

a(n) = Sum_{1*s_1+2*s_2+...=n} (fixA[s_1, s_2, ...]/ (1^s_1*s_1!*2^s_2*s_2!*...)) where fixA[s_1, s_2, ...] = 3^Sum_{i, j>=1} (gcd(i,j)*s_i*s_j).

More terms from Vladeta Jovovic, Jan 14 2000

Formula from Christian G. Bower, Jan 06 2004

A326220 Number of non-Hamiltonian labeled n-vertex digraphs (with loops).

Original entry on oeis.org

1, 0, 12, 392, 46432, 20023232, 30595305216

Offset: 0

Gus Wiseman, Jun 15 2019

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

			The a(2) = 12 digraph edge-sets:
  {}  {11}  {11,12}  {11,12,22}
      {12}  {11,21}  {11,21,22}
      {21}  {11,22}
      {22}  {12,22}
            {21,22}

Wikipedia, Hamiltonian path

The unlabeled case is A326223.
The undirected case is A326239 (with loops) or A326207 (without loops).
The case without loops is A326218.
Digraphs (with loops) containing a Hamiltonian cycle are A326204.
Digraphs (with loops) not containing a Hamiltonian path are A326213.
Cf. A000595, A002416, A003024, A003216, A246446, A326208, A326219, A326222, A326224.

Table[Length[Select[Subsets[Tuples[Range[n],2]],FindHamiltonianCycle[Graph[Range[n],DirectedEdge@@@#]]=={}&]],{n,4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 46336 which is incorrect *)

a(5)-a(6) from Bert Dobbelaere, Jun 11 2024

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

Original entry on oeis.org

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.

A000662 Number of relations with 3 arguments on n nodes.

Original entry on oeis.org

2, 136, 22377984, 768614354122719232, 354460798875983863749270670915141632, 146267071761884981524915186989628577728537526896649216991428608

Offset: 1

N. J. A. Sloane

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 76 (2.2.31)
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
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..15
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, A001377, A051241.

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

a(n) = Sum_{1*s_1+2*s_2+...=n} (fixA[s_1, s_2,...]/(1^s_1*s_1!*2^s_2*s_2!*...)) where fixA[s_1, s_2, ...] = 2^Sum_{i, j, k>=1} (i*j*k*s_i*s_j*s_k/lcm(i, j, k)). - Christian G. Bower, Jan 06 2004

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

Original entry on oeis.org

1, 2, 4, 128, 12352, 3826272, 3775441536

Offset: 0

Gus Wiseman, Jun 15 2019

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

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

The unlabeled case is A326224.
The case without loops is A326216.
Digraphs containing a Hamiltonian path are A326214.
Digraphs not containing a Hamiltonian cycle are A326220.
Cf. A000595, A002416, A003024, A003216, A057864, A283420, A326204, A326206, A326221.

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

A002416(n) = a(n) + A326214(n).

a(5)-a(6) from Bert Dobbelaere, Jun 11 2024

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

Original entry on oeis.org

0, 0, 3, 48, 3324, 929005, 1014750550, 4305572108670

Offset: 0

Gus Wiseman, Jun 15 2019

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

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

The undirected case is A326206.
The unlabeled undirected case is A057864.
The case with loops is A326214.
Unlabeled digraphs with a Hamiltonian path are A326221.
Digraphs (without loops) not containing a Hamiltonian path are A326216.
Digraphs (without loops) containing a Hamiltonian cycle are A326219.
Cf. A000595, A002416, A003024, A003216, A283420, A326204, A326208, A326213, 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) + A326216(n).

a(5)-a(7) from Bert Dobbelaere, Feb 21 2023

A326218 Number of non-Hamiltonian labeled n-vertex digraphs (without loops).

Original entry on oeis.org

1, 0, 3, 49, 2902

Offset: 0

Gus Wiseman, Jun 15 2019

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

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

Wikipedia, Hamiltonian path

The unlabeled case is A326222.
The undirected case is A326207.
The case with loops is A326220.
Digraphs (without loops) containing a Hamiltonian cycle are A326219.
Digraphs (without loops) not containing a Hamiltonian path are A326216.
Cf. A000595, A002416, A003024, A003216, A246446, A326204, A326213, A326223, A326225.

Table[Length[Select[Subsets[Select[Tuples[Range[n],2],UnsameQ@@#&]],FindHamiltonianCycle[Graph[Range[n],DirectedEdge@@@#]]=={}&]],{n,4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 2896 which is incorrect *)

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

A326219 Number of labeled n-vertex Hamiltonian digraphs (without loops).

Original entry on oeis.org

0, 1, 1, 15, 1194

Offset: 0

Gus Wiseman, Jun 15 2019

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

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

Wikipedia, Hamiltonian path

The unlabeled case is A326225.
The undirected case is A326208 (without loops) or A326240 (with loops).
The case with loops is A326204.
Digraphs (without loops) not containing a Hamiltonian cycle are A326218.
Digraphs (without loops) containing a Hamiltonian path are A326217.
Cf. A000595, A002416, A003024, A003216, A053763, A246446, A326220, A326226.

Table[Length[Select[Subsets[Select[Tuples[Range[n],2],UnsameQ@@#&]],FindHamiltonianCycle[Graph[Range[n],DirectedEdge@@@#]]!={}&]],{n,0,4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 1200 which is incorrect *)

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

A001173 Half the number of binary relations on n unlabeled points.

Original entry on oeis.org

1, 5, 52, 1522, 145984, 48464496, 56141454464, 229148550030864, 3333310786076963968, 174695272746749919580928, 33301710992539090379269318144, 23278728241293494533015563325552128, 60084295633556503802059558812644803074048, 576025077880237078776946730871618386151571214336

Offset: 1

N. J. A. Sloane

M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sept. 15, 1955, pp. 14-22.
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).

Chai Wah Wu, Table of n, a(n) for n = 1..59
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.

Cf. A000595, A001174.

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_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/(2 n!)];
Array[a, 12] (* Jean-François Alcover, Aug 01 2019, after Andrew Howroyd in A000595 *)

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

a(n) = A000595(n)/2. - Sean A. Irvine, Mar 16 2012

More terms from Vladeta Jovovic, Apr 18 2000

a(13)-a(14) (based on A000595) from Pontus von Brömssen, Aug 04 2022

A326214 Number of labeled n-vertex digraphs (with loops) containing a (directed) Hamiltonian path.

Original entry on oeis.org

0, 0, 12, 384, 53184

Offset: 0

Gus Wiseman, Jun 15 2019

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

			The a(2) = 12 edge-sets:
  {12}
  {21}
  {11,12}
  {11,21}
  {12,21}
  {12,22}
  {21,22}
  {11,12,21}
  {11,12,22}
  {11,21,22}
  {12,21,22}
  {11,12,21,22}

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

The unlabeled case is A326221.
The undirected case is A326206.
The case without loops is A326217.
Digraphs not containing a Hamiltonian path are A326213.
Digraphs containing a Hamiltonian cycle are A326204.
Cf. A000595, A002416, A003024, A003216, A057864, A326224, A326225, A326226.

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

A002416(n) = a(n) + A326213(n).

cp's OEIS Frontend

A004105 Number of point-self-dual nets with 2n nodes. Also number of directed 2-multigraphs with loops on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A326220 Number of non-Hamiltonian labeled n-vertex digraphs (with loops).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A000662 Number of relations with 3 arguments on n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326218 Number of non-Hamiltonian labeled n-vertex digraphs (without loops).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A326219 Number of labeled n-vertex Hamiltonian digraphs (without loops).

Views

Author