A003024 -id:A003024 - cp's OEIS frontend

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

0, 2, 4, 120, 19104

Offset: 0

Gus Wiseman, Jun 14 2019

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

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

Wikipedia, Hamiltonian path

The unlabeled case is A326226.
The case without loops is A326219.
The undirected case (without loops) is A326208.
Non-Hamiltonian digraphs are A326220.
Digraphs containing a Hamiltonian path are A326214.
Cf. A000595, A002416, A003024, A003216, A057864.

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

A334282 Number of properly colored labeled graphs on n nodes so that the color function is surjective onto {c_1,c_2,...,c_k} for some k, 1<=k<=n.

Original entry on oeis.org

1, 1, 5, 73, 2849, 277921, 65067905, 35545840513, 44384640206849, 124697899490480641, 778525887500557625345, 10693248499002776513697793, 320453350845793018626300755969, 20807125028666778079876193487790081, 2909872870574162514727072641529432735745

Offset: 0

Geoffrey Critzer, Apr 21 2020

nonn

Also 1 together with the row sums of A046860.

A binary relation R on [n] is periodic iff there is a d>=2 such that R^d = R. Let A be the class of non-arcless strongly connected periodic relations (A000629). Then a(n) is the number of binary relations on [n] whose strongly connected components are in A. - Geoffrey Critzer, Dec 12 2023

Alois P. Heinz, Table of n, a(n) for n = 0..77

Cf. A046860, A322280, A011266, A361560, A003024, A365534, A365590.

b:= proc(n, k) option remember; `if`([n, k]=[0$2], 1,
      add(binomial(n, r)*2^(r*(n-r))*b(r, k-1), r=0..n-1))
    end:
a:= n-> add(b(n,k), k=0..n):
seq(a(n), n=0..15);  # Alois P. Heinz, Apr 21 2020

nn = 15; e2[x_] := Sum[x^n/(n! 2^Binomial[n, 2]), {n, 0, nn}];
Table[n! 2^Binomial[n, 2], {n, 0, nn}] CoefficientList[Series[1/(1 - (e2[x] - 1)), {x, 0, nn}], x]

Sum_{n>=0} a_n*x^n/(n!*2^C(n,2)) = 1/(2-Sum_{n>=0} x^n/(n!*2^C(n,2))).

A082402 Number of n-node labeled weakly connected acyclic digraphs.

Original entry on oeis.org

0, 1, 2, 18, 446, 26430, 3596762, 1111506858, 774460794326, 1206342801843750, 4162927142993589122, 31557464707483035620178, 521560130632321900618457246, 18669813048017298278379855511470

Offset: 0

Vladeta Jovovic, Apr 15 2003

nonn

R. W. Robinson, Counting labeled acyclic digraphs, pp. 263-264 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.

Andrew Howroyd, Table of n, a(n) for n = 0..50
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.

Cf. A003024.

\\ here G(n) is A003024 as e.g.f.
G(n)={my(v=vector(n+1)); v[1]=1; for(n=1, n, v[n+1]=sum(k=1, n, -(-1)^k*2^(k*(n-k))*v[n-k+1]/k!))/n!; Ser(v)}
{ concat([0], Vec(serlaplace(log(G(15))))) } \\ Andrew Howroyd, Sep 10 2018

E.g.f.: log(B(x)) where B(x) is e.g.f. for A003024.

a(n) = A003024(n) - Sum_{k=1..n-1} binomial(n-1, k-1)*a(k)*A003024(n-k).

A089482 Number of real {0,1}-matrices having permanent = 1.

Original entry on oeis.org

1, 1, 6, 150, 13032, 3513720, 2722682160, 5739447495600, 31598877919109760, 440333998013384657280, 15150599165671354541318400, 1261508968034974650352062240000, 250009928097136435131869478983500800, 116299581308873767293693697630883742796800

Offset: 0

Hugo Pfoertner, Nov 05 2003

nonn

The following is Max Alekseyev's proof of the formula: Suppose that we have a (0,1)-matrix M with permanent equal to 1. Then in M there is a unique set of n elements, each equal to 1, whose product makes the permanent equal 1. Permute the columns of M so that these n elements become arranged along the main diagonal, and denote the resulting matrix by M'. It is clear that each M' corresponds to n! different matrices M (this is where the factor n! in the formula comes from).
Let M'' be the same as M' except for zeros on the main diagonal. Then the permanent of M'' is zero. Viewing M'' as an adjacency matrix of a directed graph G, we notice that G cannot have a cycle. Indeed, if there is a cycle x_1 -> x_2 -> ... -> x_k -> x_1, then the set of elements (x_1,x_2), (x_2,x_3), ..., (x_k,x_1) together with (y_1,y_1), ..., (y_{n-k},y_{n-k}), where { y_1, ..., y_{n-k} } is the complement of { x_1, ..., x_k } in the set { 1, 2, ..., n }, form a set of elements of the matrix M' whose product is 1, making the permanent of M' greater than 1.
This works in the reverse direction as well, resulting in the statement: The permanent of M' is 1 if and only if M'' represents the adjacency matrix of some DAG. Therefore there exist A003024(n) distinct matrices M'. - Vladeta Jovovic, Oct 27 2009

			a(2) = 6 because there are 6 matrices ((1,0),(0,1)), ((0,1),(1,0)), ((0,1),(1,1)), ((1,0),(1,1)), ((1,1),(0,1)), ((1,1),(1,0)) with permanent = 1.

Alois P. Heinz, Table of n, a(n) for n = 0..73

Cf. A088672 number of (0,1)-matrices with zero permanent, A089479 occurrence counts for permanents of all (0,1)-matrices, A089480 occurrence counts for permanents of non-singular (0,1)-matrices.

Cf. A000142, A003024, A227414 number of (0,1)-matrices with permanent greater than zero.

b:= proc(n) option remember; `if`(n=0, 1, add((-1)^(k+1)*
      binomial(n, k)*2^(k*(n-k))*b(n-k), k=1..n))
    end:
a:= n-> n!*b(n):
seq(a(n), n=0..14);  # Alois P. Heinz, Jun 27 2023

A003024[n_] := A003024[n] = If[n == 0 || n == 1, 1, Sum[-(-1)^k*
   Binomial[n, k]*2^(k*(n - k))*A003024[n - k], {k, 1, n}]];
a[n_] := n! * A003024[n];
Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Sep 20 2024 *)

a(n) = n! * A003024(n). - Vladeta Jovovic, Oct 26 2009

a(6) from Gordon F. Royle
More terms from Vladeta Jovovic, Oct 26 2009
a(0)=1 prepended by Alois P. Heinz, Jun 27 2023

A058876 Triangle read by rows: T(n,k) = number of labeled acyclic digraphs with n nodes, containing exactly n+1-k points of in-degree zero (n >= 1, 1<=k<=n).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Jan 07 2001

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

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).
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.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
R. W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)

Columns give A058877, A060337.
Diagonals give A003025, A003026, A060335.
Row sums give A003024.
Cf. A122078 (unlabeled case).

a[p_, k_] :=a[p, k] =If[p == k, 1, Sum[Binomial[p, k]*a[p - k, n]*(2^k - 1)^n*2^(k (p - k - n)), {n,1, p - k}]];
Map[Reverse, Table[Table[a[p, k], {k, 1, p}], {p, 1, 6}]] // Grid (* Geoffrey Critzer, Aug 29 2016 *)

A058876(n)={my(v=vector(n)); for(n=1, #v, v[n]=vector(n, i, if(i==n, 1, my(u=v[n-i]); sum(j=1, #u, 2^(i*(#u-j))*(2^i-1)^j*binomial(n,i)*u[j])))); v}
{ my(T=A058876(10)); for(n=1, #T, print(Vecrev(T[n]))) } \\ Andrew Howroyd, Dec 27 2021

Harary and Prins (following Robinson) give a recurrence.

More terms from Vladeta Jovovic, Apr 10 2001

A188457 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1 + 3^nx)^(n+1).

Original entry on oeis.org

1, 1, 5, 109, 9449, 3068281, 3586048685, 14668583277349, 205716978569685329, 9737002299093315531121, 1536239893108209683958428885, 799846636937376803320381186364509, 1362900713950636674946135205457794784569

Offset: 0

Paul D. Hanna, Mar 31 2011

G.f. satisfies a variant of an identity involving A003024:
1 = Sum_{n>=0} A003024(n)*x^n/(1 + 2^n*x)^(n+1),
where A003024(n) is the number of acyclic digraphs with n labeled nodes.
a(n) is the number of acyclic 2-multidigraphs. Cf. A137435, A339768. - Geoffrey Critzer, Feb 21 2021

			Illustration of the generating functions.
E.g.f.: 1 = exp(-x) + exp(-3*x)*x + 5*exp(-9*x)*x^2/2! + 109*exp(-27*x)*x^3/3! +...
L.g.f.: log(1+x) = x/(1+3*x) + 5*(x^2/2)/(1+9*x)^2 + 109*(x^3/3)/(1+27*x)^3 +...
G.f.: 1 = 1/(1+x) + 1*x/(1+3*x)^2 + 5*x^2/(1+9*x)^3 + 109*x^3/(1+27*x)^4 +...
G.f.: 1 = 1/(1+x)^2 + 1*2*x/(1+3*x)^3 + 5*3*x^2/(1+9*x)^4 + 109*4*x^3/(1+27*x)^5 +...
G.f.: 1 = 1/(1+x)^3 + 1*3*x/(1+3*x)^4 + 5*6*x^2/(1+9*x)^5 + 109*10*x^3/(1+27*x)^6 +...

Seiichi Manyama, Table of n, a(n) for n = 0..62

Cf. A003024, A137435, A188456, A188455, A135079.

Cf. A137435, A339768.

a[n_] := a[n] = If[n == 0, 1, Sum[-(-1)^k Binomial[n, k] 3^(k(n-k)) a[n-k], {k, 1, n}]];
a /@ Range[0, 12] (* Jean-François Alcover, Nov 02 2019 *)

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+3^k*x+x*O(x^n))^(k+1)), n)}
for(n=0,20, print1(a(n),", "))

/* Holds for m>=1: */
{a(n)=local(m=1);polcoeff(1-sum(k=0, n-1, a(k)*binomial(m+k-1,k)*x^k/(1+3^k*x+x*O(x^n))^(k+m)), n)/binomial(m+n-1,n)}
for(n=0,20, print1(a(n),", "))

/* Recurrence: */
{a(n)=if(n<1, n==0, sum(k=1, n, -(-1)^k*binomial(n, k)*3^(k*(n-k))*a(n-k)))}
for(n=0,20, print1(a(n),", "))

/* E.g.f.: */
{a(n)=n!*polcoeff(1-sum(k=0, n-1, a(k)*exp(-3^k*x+x*O(x^n))*x^k/k!), n)}
for(n=0,20, print1(a(n),", "))

G.f.: 1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + 3^n*x)^(n+m) for m>=1.
L.g.f.: log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 3^n*x)^n.
E.g.f.: 1 = Sum_{n>=0} a(n)*exp(-3^n*x)*x^n/n!.
a(n) = Sum_{k=1..n} (-1)^(k+1)*C(n, k)*3^(k*(n-k))*a(n-k) for n>0 with a(0)=1.
From Peter Bala, Apr 01 2013: (Start)
Let E(x) = sum {n >= 0} x^n/(n!*3^C(n,2)). Then a generating function for this sequence is 1/E(-x) = sum {n >= 0} a(n)*x^n/(n!*3^C(n,2)) = 1 + x + 5*x^2/(2!*3) + 109*x^3/(3!*3^3) + 9449*x^4/(4!*3^6) + .... (End)
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 3*x^2 + 39*x^3 + 2403*x^4 + 616131*x^5 + ... appears to have integer coefficients. - Peter Bala, Jan 14 2016

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

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).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A334282 Number of properly colored labeled graphs on n nodes so that the color function is surjective onto {c_1,c_2,...,c_k} for some k, 1<=k<=n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A082402 Number of n-node labeled weakly connected acyclic digraphs.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

A089482 Number of real {0,1}-matrices having permanent = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A058876 Triangle read by rows: T(n,k) = number of labeled acyclic digraphs with n nodes, containing exactly n+1-k points of in-degree zero (n >= 1, 1<=k<=n).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A188457 G.f.: 1 = Sum_{n>=0} a(n)*x^n/(1 + 3^n*x)^(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

A188457 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1 + 3^nx)^(n+1).