A002416 -id:A002416 - cp's OEIS frontend

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

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

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

A326252 Number of digraphs with vertices {1..n} whose increasing edges are crossing.

Original entry on oeis.org

0, 0, 0, 0, 16384, 22020096, 62679678976, 556181084962816

Offset: 0

Gus Wiseman, Jun 30 2019

A directed edge (a,b) is increasing if a < b. Two edges (a,b), (c,d) are crossing if a < c < b < d or c < a < d < b.

Simple graphs whose edges are crossing are A326210.
Digraphs whose increasing edges are not crossing are A326251.
Digraphs whose edges are not crossing are A326237.
Cf. A002416, A002720, A229865, A324170, A326209, A326252, A326258.

croXQ[eds_]:=MatchQ[eds,{_,{x_,y_},_,{z_,t_},_}/;x

a(n) = 2^(n * (n + 1)/2) * A326210(n).

A227414 Number of ordered n-tuples of subsets of {1,2,...,n} which satisfy the conditions in Hall's Marriage Problem.

Original entry on oeis.org

1, 1, 7, 247, 37823, 23191071, 54812742655, 494828369491583

Offset: 0

Geoffrey Critzer, Jul 10 2013

In a group of n women and n men, each woman selects a subset of men that she would happily marry.  Hall's marriage problem gives the conditions on the subsets so that every woman can become happily married.
a(n)/2^(n^2) is the probability that if the subsets are selected at random then all the women can be happy.
Equivalently, a(n) is the number of n x n {0,1} matrices such that if in any arbitrarily selected r rows we note the columns that have at least one 1 in the selected rows then the number of such columns must not be less than r.

			a(2) = 7 because we have:
1: ({1}, {2});
2: ({1}, {1,2});
3: ({2}, {1});
4: ({2}, {1,2});
5: ({1,2}, {1});
6: ({1,2}, {2});
7: ({1,2}, {1,2}).

F. Hivert, J. D. Mitchell, F. L. Smith, and W. A. Wilson, Minimal generating sets for matrix monoids, arXiv:2012.10323 [math.RA], 2020, p. 2.
Alexander Postnikov, Permutohedra, associahedra, and beyond, 2005, arXiv:math/0507163 [math.CO], 2005.
Stefan Schwarz, The semigroup of fully indecomposable relations and Hall relations, Czechoslovak Mathematical Journal, 23 (1973), 151-163.
Wikipedia, Hall's marriage theorem

Cf. A002416, A088672, A089482, A089479.

f[list_]:=Apply[And,Flatten[Table[Map[Length[#]>=n&,Map[Apply[Union,#]&, Subsets[list,{n}]]],{n,1,Length[list]}]]]; Table[Total[Boole[Map[f, Tuples[Subsets[n],n]]]],{n,1,4}]

a(n) = A002416(n) - A088672(n).

a(n) = Sum_{k=1..n!} A089479(n,k). - Geoffrey Critzer, Dec 20 2023

a(5) from James Mitchell, Nov 13 2015
a(6) from James Mitchell, Nov 16 2015
a(7) from Noam Zeilberger, Jun 04 2019
a(0)=1 prepended by Alois P. Heinz, Dec 19 2023

A242876 Number of n X n nonograms (hanjie) which can be solved uniquely.

Original entry on oeis.org

1, 2, 14, 384, 52362, 25309575, 49745060669

Offset: 0

Charles R Greathouse IV and Sophia Greathouse, May 25 2014

In this game there is an n X n grid where each square may or may not be filled. Each column and each row is labeled by the length of each successive block of filled squares, but without indication of the number of unfilled squares in between. The object is to determine which squares are filled.
100% of the 1 X 1 grids can be solved uniquely. 87.5% of the 2 X 2 grids can be solved uniquely. 75% of the 3 X 3 grids can be solved uniquely. About 80% of the 4 X 4 grids can be solved uniquely.
About 75% of the 5 X 5 grids can be solved uniquely, and about 72% of the 6 X 6 grids can be solved uniquely. - Charles R Greathouse IV, Apr 22 2015
Ueda & Nagao show that determining uniqueness for a nonogram, given its hint sequence, is NP-complete. - Charles R Greathouse IV, Oct 28 2022

			There are two 1 X 1 grids, filled and unfilled, and both can be distinguished, so a(1) = 2.
Of the 16 2 X 2 grids, only 10/01 and 01/10 cannot be distinguished (both have one block of length 1 for each row and column) and so a(2) = 14.

N Ueda and T Nagao, NP-completeness results for NONOGRAM via parsimonious reductions, unpublished technical report (1996).

Bertram Felgenhauer, Counting Nonograms
Wikipedia, Nonogram

Cf. A384764 (number of n X m nonograms which can be solved uniquely).
Cf. A002416 (number of n X n nonograms).
Cf. A000079 (number of 1 X n nonograms which can be solved uniquely; they are fully determined by the n column hints).
Cf. A000045.

nono(v)=my(u=List(),t); for(i=1,#v,if(v[i],t++,if(t,listput(u,t);t=0))); if(t,listput(u,t)); Vec(u);
nonomat(M)=vector(matsize(M)[1],i,nono(M[i,]));
nono2(M)=[nonomat(M),nonomat(M~)];
num2mat(d,n)=matrix(d,d,i,j,bittest(n,(i-1)*d+j-1));
a(n)=my(v=vector(2^n^2,i,nono2(num2mat(n,i)))); v=vecsort(v,lex); sum(i=2,#v-1,v[i]!=v[i-1] && v[i]!=v[i+1])+(v[1]!=v[2])+(v[#v]!=v[#v-1]);

a(n) >= F(n)^2 * a(n-1), since there are F(n) ways to fill the last row (resp., column) such that the first and last squares are filled and no consecutive squares are unfilled. These configurations can be solved without looking at the other rows or columns and so allow expanding an (n-1) X (n-1) configuration to an n X n configuration. Thus a(n) >> phi^(n*(n+1))/5^n. (F(n) is the n-th Fibonacci number, A000045.) - Charles R Greathouse IV, Sep 02 2014 [Corrected by Bertram Felgenhauer, Jun 09 2025]

a(5) from Mark E. Shoulson, Aug 13 2014
a(6) from Karl W. Heuer, Jan 29 2015
a(0) = 1 prepended and a(6) corrected by Bertram Felgenhauer, Jun 08 2025

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

A326251 Number of digraphs with vertices {1..n} whose increasing edges are not crossing.

Original entry on oeis.org

1, 2, 16, 512, 49152, 11534336, 6039797760, 6768868458496, 15885743998107648, 77083611222073409536, 767126299049285413502976, 15572324598183490228037091328, 642316330843573124053884695740416, 53681919993405760099480940765478125568

Offset: 0

Gus Wiseman, Jun 30 2019

nonn

A directed edge (a,b) is increasing if a < b. Two edges (a,b), (c,d) are crossing if a < c < b < d or c < a < d < b.

Conjecture: Also the number of non-nesting digraphs with vertices {1..n} whose increasing edges are not crossing, where two edges (a,b), (c,d) are nesting if a < c < d < b or c < a < b < d.

Simple graphs whose edges are non-crossing are A054726.
Digraphs whose edges are not crossing are A326237.
Digraphs whose increasing edges are crossing are A326252.
Cf. A002416, A229865, A324170, A326209, A326250, A326251.

croXQ[eds_]:=MatchQ[eds,{_,{x_,y_},_,{z_,t_},_}/;x

a(n) = 2^(n * (n + 1)/2) * A054726(n).

A344113 a(n) = 2^(n^2) - n^n.

Original entry on oeis.org

1, 12, 485, 65280, 33551307, 68719430080, 562949952597769, 18446744073692774400, 2417851639229257961991863, 1267650600228229401486703205376, 2658455991569831745807613835249018541, 22300745198530623141535718272639445405532160

Offset: 1

Mohammad K. Azarian, May 14 2021

a(n) is the number of relations on a set with n elements that are not functions.

			a(1) = 2^(1^2) - 1^1 = 1.
a(2) = 2^(2^2) - 2^2 = 12.
a(3) = 2^(3^2) - 3^3 = 485.

Michael De Vlieger, Table of n, a(n) for n = 1..57
Mohammad K. Azarian, Remarks and Conjectures Regarding Combinatorics of Discrete Partial Functions, Int'l Math. Forum (2022) Vol. 17, No. 3, 129-141.

Cf. A000312, A002416, A036679, A344110, A344112, A344114.

Table[2^(n^2) - n^n, {n, 12}] // Flatten

A064231 Triangle read by rows: T(n,k) = number of rational (+1,-1) matrices of rank k (n >= 1, 1 <= k <= n).

Original entry on oeis.org

2, 8, 8, 32, 288, 192, 128, 6272, 36864, 22272, 512, 115200, 3456000, 18432000, 11550720, 2048, 1968128, 243302400, 6471168000, 36373708800, 25629327360, 8192, 32514048, 14809546752, 1557061632000, 43378316083200, 281770208133120

Offset: 1

N. J. A. Sloane, Sep 23 2001

Rows add to 2^(n^2) = A002416. - Jonathan Vos Post, Feb 27 2011

Komlos and later Kahn, Komlos and Szemeredi show that almost all such matrices are invertible.

			2; 8,8; 32,288,192; 128,6272,36864,22272; ...

J. Kahn, J. Komlos and E. Szemeredi: On the probability that a random +-1 matrix is singular, J. AMS 8 (1995), 223-240.
J. Komlos, On the determinants of random matrices, Studia Sci. Math. Hungar., 3 (1968), 387-399.

Cf. A064230, A000409, A000410, A046747.

T=matrix(4,4); { for(n=1,4, mm=matrix(n,n); for(k=1,n, T[n,k]=0); forvec(x=vector(n*n,i,[0,1]), for(i=1,n, for(j=1,n,mm[i,j]=(-1)^x[i+n*(j-1)])); T[n,matrank(mm)]++); for(k=1,n,print1(T[n,k], if(k

More terms and PARI code from Michael Somos, Sep 25 2001
More terms from Vladeta Jovovic, Apr 02 2006
Offset changed to 1 by T. D. Noe, Mar 02 2011

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A326252 Number of digraphs with vertices {1..n} whose increasing edges are crossing.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A227414 Number of ordered n-tuples of subsets of {1,2,...,n} which satisfy the conditions in Hall's Marriage Problem.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A242876 Number of n X n nonograms (hanjie) which can be solved uniquely.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A326251 Number of digraphs with vertices {1..n} whose increasing edges are not crossing.

Views

Author

Keywords