A002416 -id:A002416 - cp's OEIS frontend

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

0, 1, 1, 4, 61, 3725, 844141, 626078904

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(3) = 4 digraph edge-sets:
  {12,23,31}
  {12,13,21,32}
  {12,13,21,23,31}
  {12,13,21,23,31,32}

Sean A. Irvine, Non-isomorphic representatives of the a(5) = 3725 non-Hamiltonian digraphs (without loops)
Gus Wiseman, Non-isomorphic representatives of the a(4) = 61 non-Hamiltonian digraphs (without loops)

The labeled case is A326219.
The case with loops is A326226.
The undirected case is A003216.
Non-Hamiltonian unlabeled digraphs (without loops) are A326222.
Cf. A000595, A002416, A003087, A003216, A053763, A246446, A326204, A326218, A326223.

a(5)-a(7) from Sean A. Irvine, Jun 16 2019

A326237 Number of non-nesting digraphs with vertices {1..n}, where two edges (a,b), (c,d) are nesting if a < c and b > d or a > c and b < d.

Original entry on oeis.org

1, 2, 12, 104, 1008, 10272, 107712, 1150592

Offset: 0

Gus Wiseman, Jun 19 2019

These are digraphs with the property that, if the edges are listed in lexicographic order, the sequence of targets is weakly increasing. For example, the digraph with lexicographically ordered edge set {(1,2),(2,1),(3,1),(3,2)} is nesting because the targets are (2,1,1,2), a sequence that is not weakly increasing.
Also the number of non-semicrossing digraphs with vertices {1..n}, where two edges (a,b), (c,d) are semicrossing if a < c and b < d or a > c and b > d. For example, the a(2) = 4 non-semicrossing digraph edge-sets are:
  {}
  {11}
  {12}
  {21}
  {22}
  {11,12}
  {11,21}
  {12,21}
  {12,22}
  {21,22}
  {11,12,21}
  {12,21,22}
Apparently a duplicate of A152254. - R. J. Mathar, Jul 12 2019

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

Nesting digraphs are A326209.
Non-nesting set partitions are A000108.
Non-capturing set partitions are A054391.
Cf. A002416, A002720, A054391, A058681, A122880, A229865.
Cf. A326249, A326250, A326251, A326256, A326257.

Table[Length[Select[Subsets[Tuples[Range[n],2]],OrderedQ[Last/@#]&]],{n,4}]

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

A060656 a(n) = 2a(n-1)a(n-2)/a(n-3), with a(0)=a(1)=1.

Original entry on oeis.org

1, 1, 2, 4, 16, 64, 512, 4096, 65536, 1048576, 33554432, 1073741824, 68719476736, 4398046511104, 562949953421312, 72057594037927936, 18446744073709551616, 4722366482869645213696, 2417851639229258349412352

Offset: 0

Henry Bottomley, Apr 18 2001

a(n+1) is the Hankel transform of A135052. - Paul Barry, Nov 15 2007
a(n+1) is the Hankel transform of the aerated large Schroeder numbers. a(n) and a(n+1) both satisfy the trivial Somos-4 recurrence u(n)=4*u(n-2)^2/u(n-4). Associated with the elliptic curve y^2=1-6x^2+x^4 via Schroeder numbers. - Paul Barry, Dec 08 2009
Hankel transform of A089324. - Paul Barry, Mar 01 2010
a(n+1) is the number of n X n binary matrices that are symmetric about both diagonals (bisymmetric). For the derivation of this result, see the link below. - Dennis P. Walsh, Apr 03 2014
1 followed by {a(n-1)}A078495).%20-%20_Vladimir%20Shevelev">(n>=1) is the Somos-3 sequence: b(0)=b(1)=b(2)=1;for n>=3, b(n)=2*b(n-1)*b(n-2)/b(n-3) (cf. comment in A078495). - _Vladimir Shevelev, Apr 20 2016
If the Hankel transform is defined as in the link 'Sequence transformations' then a(n) is the Hankel transform of A151374. - Peter Luschny, Nov 30 2016

			a(6) = 2*64*16/4 = 512.
G.f. = 1 + x + 2*x^2 + 4*x^3 + 16*x^4 + 64*x^5 + 512*x^6 + 4096*x^7 + ...

Harry J. Smith, Table of n, a(n) for n = 0..100
Peter Luschny, Sequence transformations
Dennis P. Walsh, Notes on binary bisymmetric matrices

Cf. A002416, A002620, A016116, A038754, A089324, A135052, A262666, A078495, A151374.

A060656:=n->2^floor(n^2/4); seq(A060656(n), n=0..20); # Wesley Ivan Hurt, Apr 30 2014

a[ n_] := 2^Quotient[n^2, 4]; (* Michael Somos, Jan 24 2014 *)
nxt[{a_,b_,c_}]:={b,c,(2c*b)/a}; NestList[nxt,{1,1,2},20][[All,1]] (* Harvey P. Dale, Nov 26 2017 *)

{ for (n=0, 100, write("b060656.txt", n, " ", 2^(n^2\4)); ) } \\ Harry J. Smith, Jul 09 2009

{a(n) = 2^(n^2\4)}; /* Michael Somos, Jan 24 2014 */

a(n) = 2^floor( n^2/4 ) = a(n - 1) * 2^floor( n/2 ) = a(n - 2) * 2^(n - 1) = a(n - 1) * A016116(n) = 2^A002620(n).
0 = a(n) * a(n+3) + a(n+1) * ( -2*a(n+2) ) for all n in Z. - Michael Somos, Jan 24 2014
0 = a(n) * a(n+4) + a(n+2) * ( -4*a(n+2) ) for all n in Z. - Michael Somos, Jan 24 2014

A229865 Number of n X n 0..1 arrays with corresponding row and column sums equal.

Original entry on oeis.org

1, 2, 8, 80, 2432, 247552, 88060928, 112371410944, 523858015518720, 9041009511609073664, 583447777113052431515648, 141885584718620229407228821504, 130832005909904417592540055577034752, 459749137931232137234615429529864283095040, 6182706200522446492946534924719926752508110700544

Offset: 0

R. H. Hardin, Oct 01 2013

nonn

Also known as labeled Eulerian digraphs allowing loops. - Brendan McKay, May 12 2019

			Some solutions for n=4:
  0 0 0 1     0 0 1 0     0 0 0 1     0 0 1 0     0 0 1 1
  0 1 0 0     1 0 0 0     1 0 1 0     0 0 1 1     1 0 0 1
  0 0 0 1     0 1 0 0     0 1 0 1     0 1 1 1     1 1 1 0
  1 0 1 0     0 0 0 1     0 1 1 0     1 1 0 0     0 1 1 1
From _Gus Wiseman_, Jun 22 2019: (Start)
The a(3) = 8 Eulerian digraph edge-sets:
  {}
  {11}
  {22}
  {11,22}
  {12,21}
  {11,12,21}
  {12,21,22}
  {11,12,21,22}
(End)

Mohammad Behzad Kang and Andrew Salch, The mod p cohomology of the Morava stabilizer group at large primes, arXiv:2410.24171 [math.AT], 2024. See p. 46.

Column 1 of A229870.
The unlabeled version is A308111.
Cf. A000595, A002416, A002720, A007080.
Cf. A326209, A326237, A326251, A326252, A326253.

Table[Length[Select[Subsets[Tuples[Range[n],2]],Sort[First/@#]==Sort[Last/@#]&]],{n,4}] (* Gus Wiseman, Jun 22 2019 *)

a(n) = 2^n * A007080(n). - Andrew Howroyd, Sep 11 2019

a(0)=1 prepended by Alois P. Heinz, May 14 2019

Terms a(11) and beyond from Andrew Howroyd, Sep 11 2019

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

Original entry on oeis.org

0, 2, 3, 24, 858

Offset: 0

Gus Wiseman, Jun 14 2019

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

			Non-isomorphic representatives of the a(2) = 3 digraph edge-sets:
  {12,21}
  {11,12,21}
  {11,12,21,22}

Wikipedia, Hamiltonian path
Gus Wiseman, Non-isomorphic representatives of the a(3) = 24 Hamiltonian digraphs

The labeled case is A326204.
The case without loops is A326225.
The undirected case is A003216 (without loops) or A326215 (with loops).
Unlabeled non-Hamiltonian digraphs are A326223.
Unlabeled digraphs with a Hamiltonian path are A326221.
Cf. A000595, A002416, A003087, A057864, A246446, A326208.

dinorm[m_]:=If[m=={},{},If[Union@@m!=Range[Max@@Flatten[m]],dinorm[m/. Apply[Rule,Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}],{1}]],First[Sort[dinorm[m,1]]]]];
dinorm[m_,aft_]:=If[Length[Union@@m]<=aft,{m},With[{mx=Table[Count[m,i,{2}],{i,Select[Union@@m,#1>=aft&]}]},Union@@(dinorm[#1,aft+1]&)/@Union[Table[Map[Sort,m/. {par+aft-1->aft,aft->par+aft-1},{0}],{par,First/@Position[mx,Max[mx]]}]]]];
Table[Length[Select[Union[dinorm/@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) = 867 which is incorrect *)

A328044 Number of chains of binary matrices of order n.

Original entry on oeis.org

1, 3, 299, 28349043, 21262618727925419, 426789461753903103302333992563, 576797123806621878513443912437627670334052360619, 110627172261659730424051586605958905845740712964061737226074854597705843

Offset: 0

S. R. Kannan, Rajesh Kumar Mohapatra, Oct 03 2019

nonn

For n >= 1, a(n) is the number of chains of n X n (0, 1) matrices.
a(n) is also the number of chains in the power set of n^2 elements.
a(n) is the n^2-th term of A007047.
A chain of binary (crisp or Boolean or logical) matrices of order n can be thought of as a fuzzy matrix of order n.
a(n) is the number of distinct n X n fuzzy matrices.
a(n) is the sum of the n^2-th row of triangle A038719.

Alois P. Heinz, Table of n, a(n) for n = 0..20 (first 11 terms from Rajesh Kumar Mohapatra)
S. R. Kannan and Rajesh Kumar Mohapatra, Counting the Number of Non-Equivalent Classes of Fuzzy Matrices Using Combinatorial Techniques, arXiv preprint arXiv:1909.13678 [math.GM], 2019.
V. Murali, Combinatorics of counting finite fuzzy subsets, Fuzzy Sets and Systems, 157(17)(2006), 2403-2411.
V. Murali and B. Makamba, Finite Fuzzy Sets, International Journal of General Systems, Vol. 34 (1) (2005), pp. 61-75.
R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1991), 23-31.

Cf. A000079 (subsets of an n-set), A007047 (chains in power set of an n-set).

Cf. A000290 (squares), A002416 (binary relations on an n-set), A038719 (chains of length k in poset).

# P are the polynomials defined in A007047.
A328044 := n -> 2^(n^2)*subs(x=1/2, P(n^2, x)):
seq(A328044(n), n=0..7); # Peter Luschny, Oct 10 2019

Array[2 PolyLog[-#^2, 1/2] - 1 &, 8, 0] (* Michael De Vlieger, Oct 05 2019, after Jean-François Alcover at A007047 *)
Table[2*PolyLog[-n^2, 1/2] - 1 , {n, 0, 29}]

Let T(n, k) denote the number of chains of binary matrices of order n of length k, T(0, 0) = 1, T(0, k) = 0 for k > 0, thus T(n, k) = A038719(n, k).
a(n) = Sum_{k=0..n^2} T(n, k); a(0) = 1.
a(n) = A007047(n^2) = A007047(A000290(n)).

A365534 Number of convergent Boolean relation matrices on [n].

Original entry on oeis.org

1, 2, 15, 465, 61068, 32453533, 67904955351

Offset: 0

Geoffrey Critzer, Sep 08 2023

A Boolean relation matrix R is convergent iff R^k = R^(k+1) for all sufficiently large k. In other words, iff the period of R is equal to 1. The digraph of R is such that all its maximal cyclic nets are primitive (A070322) iff R is convergent. Cf. Rosenblatt link. Also, R is convergent iff every diagonal block in its Frobenius normal form is either primitive or a 1 X 1 zero matrix, Theorem 1.1 in Gregory, Kirkland and Pullman.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
G. Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum, Vol 13 (1977), 253-259.
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Cf. A070322, A002416.

Sum_{n>=0} a_n*x^n/(n!*2^binomial(n,2)) = 1/(E(x) @ exp(-(p(x)-1+x))) where E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)), p(x) = Sum_{n>=0} A070322(n)x^n/n! and @ is the exponential Hadamard product (see Panafieu and Dovgal).

A070322(n) <= a(n) <= 2^(n^2) = A002416(n).

A067959 Number of binary arrangements without adjacent 1's on n X n torus connected ne-sw n-s nw-se.

Original entry on oeis.org

1, 7, 22, 547, 9021, 812830, 70046159, 24082448515, 10363980496342, 14228018243052057, 29400555005986658803, 166705587265151114516638, 1606507128309318588452521527, 38505096862341023166325442747581, 1696028983502674228038462924646464012

Offset: 1

R. H. Hardin, Feb 02 2002

			Neighbors for n=4 (dots represent spaces):
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\

Sean A. Irvine, Table of n, a(n) for n = 1..17
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 73.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

a(13) from Vaclav Kotesovec, Aug 22 2016
a(14) from Vaclav Kotesovec, May 24 2021
a(15) from Sean A. Irvine, Jan 14 2024

A088672 Number of n X n (0,1)-matrices with zero permanent.

Original entry on oeis.org

0, 1, 9, 265, 27713, 10363361, 13906734081, 68121583929729

Offset: 0

Michael Somos, Oct 03 2003

C. J. Everett and P. R. Stein, The asymptotic number of (0,1)-matrices with zero permanent, Disc. Math. 6 (1973), 29-34.
Index entries for sequences related to binary matrices

Cf. A089479, A089482, A227414.

a[ n_] := Count[Table[Permanent[Partition[a, n]], {a, Tuples[{0, 1}, n^2]}], 0]; (* Michael Somos, Aug 05 2018 *)

a(n) is asymptotic to n*(2^(n^2 - n + 1)). [Everett and Stein]

a(n) = A002416(n) - A227414(n). - Geoffrey Critzer, Dec 19 2023

a(5) from Jaap Spies, Nov 02 2003
a(6) from Gordon F. Royle, Nov 03 2003
a(7) added by Geoffrey Critzer, Dec 19 2023 after Noam Zeilberger in A227414.
a(0)=0 prepended by Alois P. Heinz, Dec 19 2023

A089479 Triangle T(n,k) read by rows, where T(n,k) = number of times the permanent of a real n X n (0,1)-matrix takes the value k, for n >= 0, 0 <= k <= n!.

Original entry on oeis.org

0, 1, 1, 1, 9, 6, 1, 265, 150, 69, 18, 9, 0, 1, 27713, 13032, 10800, 4992, 4254, 1440, 1536, 576, 648, 24, 288, 96, 48, 0, 72, 0, 0, 0, 16, 0, 0, 0, 0, 0, 1, 10363361, 3513720, 4339440, 2626800, 3015450, 1451400, 1872800, 962400, 1295700, 425400, 873000

Offset: 0

Hugo Pfoertner, Nov 05 2003

The last element of each row is 1, corresponding to the n X n "all 1" matrix with permanent = n!. The first 4 rows were provided by Wouter Meeussen. The 6th row was computed by Gordon F. Royle: 13906734081, 2722682160, 4513642920, 3177532800, 4466769300, 2396826720, 3710999520, 2065521600, 3253760550, 1468314000, 2641593600, 1350475200, 2210277600, 1034061120,... .

			Triangle begins:
    0,     1;
    1,     1;
    9,     6,     1;
  265,   150,    69,   18,    9,    0,    1;
27713, 13032, 10800, 4992, 4254, 1440, 1536, 576, 648, 24, 288,
                   96, 48, 0, 72, 0, 0, 0, 16, 0, 0, 0, 0, 0, 1;
  ...

Hugo Pfoertner, Table of n, a(n) for n = 0..159 (rows 0..5, flattened)

T(n,0) = A088672(n), T(n,1) = A089482(n). The n-th row of the table contains A087983(n) nonzero entries. For n>2 A089477(n) gives the position of the first zero entry in the n-th row.
Cf. A089480 (occurrence counts for permanents of non-singular (0,1)-matrices), A089481 (occurrence counts for permanents of singular (0,1)-matrices).
Cf. A000290, A038507 (row lengths), A002416 (row sums).
Cf. A036781, A089478.

From Geoffrey Critzer, Dec 20 2023: (Start)
Sum_{k=1..n!} T(n,k) = A227414(n).
For n>2, T(n,n!-(n-1)!) = n^2, the number of matrices with exactly one 0 entry. (End)

Edited by Alois P. Heinz, Dec 20 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A326237 Number of non-nesting digraphs with vertices {1..n}, where two edges (a,b), (c,d) are nesting if a < c and b > d or a > c and b < d.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A060656 a(n) = 2*a(n-1)*a(n-2)/a(n-3), with a(0)=a(1)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A229865 Number of n X n 0..1 arrays with corresponding row and column sums equal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A328044 Number of chains of binary matrices of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A365534 Number of convergent Boolean relation matrices on [n].

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A067959 Number of binary arrangements without adjacent 1's on n X n torus connected ne-sw n-s nw-se.

Views

Author

Keywords

Examples

A060656 a(n) = 2a(n-1)a(n-2)/a(n-3), with a(0)=a(1)=1.