A003024 -id:A003024 - cp's OEIS frontend

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

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

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

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

Original entry on oeis.org

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

A038379 Number of real {0,1} n X n matrices A such that M = A + A' has 2's on the main diagonal, 0's and 1's elsewhere and is positive semi-definite.

Original entry on oeis.org

1, 3, 27, 729, 52649, 9058475, 3383769523, 2520512534065

Offset: 1

N. J. A. Sloane, Jul 13 2003

Necessarily A has all 1's on the main diagonal.
A real matrix M is positive semi-definite if its eigenvalues are >= 0.
For n <= 4, a(n) equals the upper bound 3^C(n,2).
For the number of different values of symmetric parts A + A', see A085658. - Max Alekseyev, Nov 11 2006

Index entries for sequences related to binary matrices

Cf. A055165, which counts nonsingular {0, 1} matrices, A003024, which counts {0, 1} matrices with positive eigenvalues, A085656 (positive definite matrices).

Cf. A085657, A085658, A080858, A083029.

a(n) = Sum_{k=0..C(n,2)} 2^k * A083029(n,k).

Definition corrected Nov 10 2006
a(6)-a(8) from Max Alekseyev, Nov 11 2006
Edited by Max Alekseyev, Jun 05 2024

A137435 Acyclic 3-multidigraphs on n nodes.

Original entry on oeis.org

1, 1, 7, 289, 63487, 69711361, 367404658687, 9036285693861889, 1015983915928423497727, 514039127264534042076119041, 1155907276780291114251550828003327, 11436746463485293365165228859824053157889, 493776641438913029616304251647570171691844763647

Offset: 0

Jonathan Vos Post, Apr 17 2008

nonn

This is the 2nd row of Table 1, p. 3 in Liskovets. The first row is A003024.

			From _Paul D. Hanna_, Apr 01 2011: (Start)
Illustration of the generating functions.
E.g.f.: 1 = exp(-x) + exp(-4*x)*x + 7*exp(-16*x)*x^2/2! + 289*exp(-64*x)*x^3/3! + ...
L.g.f.: log(1+x) = x/(1+4*x) + 7*(x^2/2)/(1+16*x)^2 + 289*(x^3/3)/(1+64*x)^3 + ...
G.f.: 1 = 1/(1+x) + 1*x/(1+4*x)^2 + 7*x^2/(1+16*x)^3 + 289*x^3/(1+64*x)^4 + ...
G.f.: 1 = 1/(1+x)^2 + 1*2*x/(1+4*x)^3 + 7*3*x^2/(1+16*x)^4 + 289*4*x^3/(1+64*x)^5 + ...
G.f.: 1 = 1/(1+x)^3 + 1*3*x/(1+4*x)^4 + 7*6*x^2/(1+16*x)^5 + 289*10*x^3/(1+64*x)^6 + ... (End)

Vincenzo Librandi, Table of n, a(n) for n = 0..55
Valery A. Liskovets, More on counting acyclic digraphs, arXiv:0804.2496 [math.CO], 2008.

Cf. A003024, A188457.

a[n_] := a[n] = Sum[(-1)^(k+1)*Binomial[n, k]*4^(k*(n-k))*a[n-k], {k, 1, n}]; a[0]=1; Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Dec 15 2014, after Paul D. Hanna *)

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+4^k*x+x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Oct 17 2009

/* 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+4^k*x+x*O(x^n))^(k+m)), n)/binomial(m+n-1, n)} \\ Paul D. Hanna, Apr 01 2011

/* Recurrence: */
{a(n)=if(n<1, n==0, sum(k=1, n, -(-1)^k*binomial(n, k)*4^(k*(n-k))*a(n-k)))} \\ Paul D. Hanna, Apr 01 2011

/* E.g.f.: */
{a(n)=n!*polcoeff(1-sum(k=0, n-1, a(k)*exp(-4^k*x+x*O(x^n))*x^k/k!), n)} \\ Paul D. Hanna, Apr 01 2011

1 = Sum_{n>=0} a(n)*exp(-4^n*x)*x^n/n!. - Vladeta Jovovic, Apr 22 2008
1 = Sum_{n>=0} a(n)*x^n/(1 + 4^n*x)^(n+1). - Paul D. Hanna, Oct 17 2009
1 = Sum_{n>=0} a(n)*binomial(n+m-1,n)*x^n/(1 + 4^n*x)^(n+m) for m >= 1. - Paul D. Hanna, Apr 01 2011
log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 4^n*x)^n. - Paul D. Hanna, Apr 01 2011
a(n) = Sum_{k=1..n} (-1)^(k+1)*C(n, k)*4^(k*(n-k))*a(n-k) for n > 0 with a(0)=1. - Paul D. Hanna, Apr 01 2011

More terms from Vladeta Jovovic, Apr 22 2008

Offset changed to 0 by Paul D. Hanna, Apr 01 2011

A339934 Number of compatible pairs (C,O) of coloring functions C:V(G) -> {1,2} and acyclic orientations O over all simple labeled graphs G on n nodes.

Original entry on oeis.org

1, 2, 10, 122, 3550, 241442, 37717630, 13335960962, 10540951836670, 18433038372948482, 70690969784862799870, 590117604000940804208642, 10654668783476237855008899070, 413773679645643893514443704442882, 34396165393184876217278672060698755070, 6094509353603648201900616579686281530408962

Offset: 0

Geoffrey Critzer, Dec 23 2020

nonn

A pair (C,O) is compatible if for u,v in V(G), when u -> v in the orientation O then C(u) >= C(v). Note that C is not necessarily a proper coloring of the vertices.

			a(2) = 10:  There are A003024(2)=3 acyclic orientations of the labeled graphs on 2 nodes.  These are paired with the 2^2=4 colorings for a total of 12 possible pairs.  All except for two of these are compatible. With V(G) = {v_1,v_2} the bad pairs are: v_2 (colored with 0) -> v_1 (colored with 1) and v_1 (colored with 0) -> v_2 (colored with 1).

Alois P. Heinz, Table of n, a(n) for n = 0..78
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.

Cf. A219765, A003024.

Row sums of A380336.

R:= proc(n) option remember; `if`(n=0, 1, expand(x*add(
      binomial(n-1, k)*2^(k*(n-k))*subs(x=x-1, R(k)), k=0..n-1)))
    end:
a:= n-> abs(subs(x=-2, R(n))):
seq(a(n), n=0..15);  # Alois P. Heinz, Jan 22 2025

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

Let E(x) = Sum_{n>=0} x^n/(2^binomial(n,2)*n!). Then Sum_{n>=0} a(n) * x^n/(2^binomial(n,2)*n!) = 1/E(-x)^2.

a(n) = (-1)^n*p_n(-2) where p_n(x) is the n-th polynomial described in A219765.

A086264 Number of real {0,1} n X n matrices having determinant=1.

Original entry on oeis.org

1, 1, 3, 84, 10020, 4851360, 9240051240, 67745781734400, 1883481284085791040

Offset: 0

Hugo Pfoertner, Oct 05 2003

Hugo Pfoertner, Determinants of (0,1)-matrices. FORTRAN program.
Minfeng Wang, C++ program
Eric Weisstein's World of Mathematics, (0,1)-Matrix.
Index entries for sequences related to binary matrices

Cf. A003024, A003432, A051752, A055165.

Cf. A046747.

a[n_] := Module[{M, iter, cnt = 0}, M = Table[a[i, j], {i, 1, n}, {j, 1, n}]; iter = Thread[{Flatten[M], 0, 1}]; Do[If[Det[M] == 1, cnt++], Evaluate[Sequence @@ iter]]; cnt];
Do[Print[n, " ", a[n]], {n, 1, 4}] (* Jean-François Alcover, Dec 09 2018 *)

a(0)=1 prepended by Alois P. Heinz, Jun 18 2022
a(7) from Minfeng Wang, Feb 09 2023
a(8) from Minfeng Wang, Apr 26 2024

A086510 Number of n X n real (0,1)-matrices with all eigenvalues >= 0.

Original entry on oeis.org

1, 2, 13, 261, 15418, 2566333

Offset: 0

Frederique Oggier (frederique.oggier(AT)epfl.ch) and N. J. A. Sloane, Sep 10 2003

			a(2)=13 because only 3 of the 16 possible matrices have eigenvalues < 0:
.
  0  1
  1  0
  with eigenvalues {1,-1}
and
  1 1
  1 0
.
  0 1
  1 1
  both with eigenvalues {1.61803..(Golden ratio),-0.61803...}

B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, arXiv:math/0310423 [math.CO], 2003.
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, J. Integer Sequences, 7 (2004), #04.3.3.
Index entries for sequences related to binary matrices

Cf. A003024, A055165, A085656, A098148.

a[0] = 1; a[n_] := Module[{M, iter, cnt = 0}, M = Table[a[i, j], {i, 1, n}, {j, 1, n}]; iter = Thread[{Flatten[M], 0, 1}]; Do[If[AllTrue[Eigenvalues[ M], NonNegative], cnt++], Evaluate[Sequence @@ iter]]; cnt];
Do[Print[n, " ", a[n]], {n, 0, 5}] (* Jean-François Alcover, Dec 09 2018 *)

a(5) from Hugo Pfoertner, Sep 26 2017

A224069 Matrix inverse of A111636.

Original entry on oeis.org

1, -1, 1, 3, -4, 1, -25, 36, -12, 1, 543, -800, 288, -32, 1, -29281, 43440, -16000, 1920, -80, 1, 3781503, -5621952, 2085120, -256000, 11520, -192, 1, -1138779265, 1694113344, -629658624, 77844480, -3584000, 64512, -448, 1, 783702329343, -1166109967360, 433693016064, -53730869248, 2491023360, -45875200, 344064, -1024, 1

Offset: 0

Peter Bala, Apr 09 2013

Let Q be the class of labeled directed acyclic graphs (dags) with some designated source nodes. Here, a source node is a node of indegree 0 and some means possibly all or none. |a(n,k)| is the number of dags in Q containing n nodes with exactly k designated source nodes. - Geoffrey Critzer, Apr 02 2023

			Triangle begins
n\k.|......0......1......2......3......4......5
= = = = = = = = = = = = = = = = = = = = = = = =
.0..|......1
.1..|.....-1......1
.2..|......3.....-4......1
.3..|....-25.....36....-12......1
.4..|....543...-800....288....-32......1
.5..|.-29281..43440.-16000...1920....-80......1
...
The sequence of zeros of R(10,x) begins 1, 3.280147..., 9.112469..., 23.366923..., 57.084317....
The sequence of zeros of R(20,x) begins 1, 3.280163..., 9.112696..., 23.369274..., 57.105379....

Vincenzo Librandi, Rows n = 0..50, flattened
W. Wang and T. Wang, Generalized Riordan array, Discrete Mathematics, Vol. 308, No. 24, 6466-6500, (2008).

Cf. A003024 (first column), A111636 (matrix inverse).

max = 8; A111636 = Table[ Binomial[n, k]*2^(k*(n - k)), {n, 0, max}, {k, 0, max}]; t = Inverse[ A111636 ]; Table[ t[[n, k]], {n, 1, max+1}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 10 2013 *)

T(n,k) = (-1)^(n-k)*A003024(n-k)*A111636(n,k) = (-1)^(n-k)*A003024(n-k)*2^(k*(n-k))*binomial(n,k).
Sum_{k = 1..n} k*2^k*T(n,k) = 0 for n >= 1.
Let E(x) = Sum_{n >= 0} x^n/(n!*2^binomial(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + .... Then a generating function for this triangle is E(x*z)/E(z) = 1 + (x - 1)*z + (x^2 - 4*x + 3)*z^2/(2!*2) + (x^3 - 12*x^2 + 36*x - 25)*z^3/(3!*2^3) + ....
This triangle is a generalized Riordan array (1/E(x), x) with respect to the sequence n!*2^C(n,2), as defined by Wang and Wang.
The row polynomials R(n,x) satisfy the recurrence equation R(n,x) = x^n - Sum_{k = 0..n-1} binomial(n,k)*2^(k*(n-k))*R(k,x) with R(0,x) = 1, as well as R'(n,2*x) = n*2^(n-1)*R(n-1,x) (the ' denotes differentiation w.r.t. x). The row polynomials appear to have only positive real zeros of multiplicity 1. Moreover, if r(n,1) < r(n,2) < ... < r(n,n) denotes the zeros of R(n,x) arranged in increasing order then it appears that lim_{n -> oo} r(n,i) exists for each fixed 1 <= i <= n. An example is given below.

A165950 Number of acyclic digraphs on n labeled nodes with one source and one sink.

Original entry on oeis.org

1, 2, 12, 216, 10600, 1306620, 384471444, 261548825328, 402632012394000, 1381332938730123060, 10440873023366019273820, 172308823347127690038311496, 6163501139185639837183141411320, 474942255590583211554917995123517868, 78430816994991932467786587093292327531620

Offset: 1

Vladeta Jovovic, Oct 01 2009

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Antoine Genitrini, Martin Pépin, and Alfredo Viola, Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling, hal-03029381 [math.CO], [cs.DM], [cs.DS], 2020.
Ira Gessel, Counting Acyclic Digraphs by Sources and Sinks
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.

The unlabeled version is A345258.

Cf. A003024, A003025, A049524, A361210.

nn = 10; B[n_] := n! 2^Binomial[n, 2];e[z_] := Sum[z^n/B[n], {n, 0, nn}];
egf[ggf_] := Normal[Series[ggf, {z, 0, nn}]] /. Table[z^i -> z^i*2^Binomial[i, 2], {i, 1, nn + 1}]; Map[ Coefficient[#, u v] &,Table[n!, {n, 0, nn}] CoefficientList[ Series[Exp[(u - 1) (v - 1) z] egf[e[(u - 1) z]*1/e[-z]*e[(v - 1) z]], {z, 0, nn}], z]] (* Geoffrey Critzer, Apr 15 2023 *)

\\ see Marcel et al. link. B(n) is A003025 as vector.
B(n)={my(a=vector(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1)*binomial(n,k)*(2^(n-k)-1)^k*a[n-k])); a}
seq(n)={my(a=vector(n), b=B(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1) * binomial(n,k) * k * (2^(n-k)-1)^k * b[n-k])); a} \\ Andrew Howroyd, Jan 01 2022

a(1)=1 inserted and terms a(13) and beyond from Andrew Howroyd, Jan 01 2022

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A038379 Number of real {0,1} n X n matrices A such that M = A + A' has 2's on the main diagonal, 0's and 1's elsewhere and is positive semi-definite.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A137435 Acyclic 3-multidigraphs on n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Formula

Extensions

A339934 Number of compatible pairs (C,O) of coloring functions C:V(G) -> {1,2} and acyclic orientations O over all simple labeled graphs G on n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A086264 Number of real {0,1} n X n matrices having determinant=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions