A287065 -id:A287065 - cp's OEIS frontend

A048291 Number of {0,1} n X n matrices with no zero rows or columns.

1, 1, 7, 265, 41503, 24997921, 57366997447, 505874809287625, 17343602252913832063, 2334958727565749108488321, 1243237913592275536716800402887, 2630119877024657776969635243647463625, 22170632855360952977731028744522744983195423

Offset: 0

Joe Keane (jgk(AT)jgk.org)

Number of relations on n labeled points such that for every point x there exists y and z such that xRy and zRx.
Also the number of edge covers in the complete bipartite graph K_{n,n}. - Eric W. Weisstein, Apr 24 2017
Counts labeled digraphs (loops allowed, no multiarcs) on n nodes where each indegree and each outdegree is >= 1. The corresponding sequence for unlabeled digraphs (1, 5, 55, 1918,... for n >= 1) seems not to be in the OEIS. - R. J. Mathar, Nov 21 2023
These relations form a subsemigroup of the semigroup of all binary relations on [n].  The zero element is the universal relation (all 1's matrix).  See Schwarz link. - Geoffrey Critzer, Jan 15 2024

			a(2) = 7:  |01|  |01|  |10|  |10|  |11|  |11|  |11|
           |10|  |11|  |01|  |11|  |01|  |10|  |11|.

Brendan McKay, Posting to sci.math.research, Jun 14 1999.

T. D. Noe, Table of n, a(n) for n = 0..32
H. Cheballah, S. Giraudo, and R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.
David Dolžan and Gabriel Verret, The automorphism group of the zero-divisor digraph of matrices over an antiring, arXiv:1908.04614 [math.AC], 2019.
R. J. Mathar, The number of nXm matrices with at most k 1's in each row or column, (2014).
Steven Schlicker, Roman Vasquez, and Rachel Wofford, Integer Sequences from Configurations in the Hausdorff Metric Geometry via Edge Covers of Bipartite Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.6.6.
Stefan Schwarz, The semigroup of fully indecomposable relations and Hall relations, Czechoslovak Mathematical Journal, 23 (1973), 151-163.
R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Edge Cover.

Cf. A054976, A104602, A283624, A287065, A173403.
Cf. A055601, A055599, A104601, A086193 (traceless, no loops), A086206, A322661 (adj. matr. undirected edges).
Diagonal of A183109.

seq(add((-1)^(n+k)*binomial(n, k)*(2^k-1)^n, k=0..n), n=0..15); # Robert FERREOL, Mar 10 2017

Flatten[{1,Table[Sum[Binomial[n,k]*(-1)^k*(2^(n-k)-1)^n,{k,0,n}],{n,1,15}]}] (* Vaclav Kotesovec, Jul 02 2014 *)

a(n)=sum(k=0,n,binomial(n,k)*(-1)^k*(2^(n-k)-1)^n)

import math
f = math.factorial
def A048291(n): return sum([(f(n)/f(s)/f(n - s))*(-1)**s*(2**(n - s) - 1)**n for s in range(0, n+1)]) # Indranil Ghosh, Mar 14 2017

a(n) = Sum_{s=0..n} binomial(n, s)*(-1)^s*2^((n-s)*n)*(1-2^(-n+s))^n.
From Vladeta Jovovic, Feb 23 2008: (Start)
E.g.f.: Sum_{n>=0} (2^n-1)^n*exp((1-2^n)*x)*x^n/n!.
a(n) = Sum_{i=0..n} Sum_{j=0..n} (-1)^(i+j)*binomial(n,i)*binomial(n,j)*2^(i*j). (End)
a(n) ~ 2^(n^2). - Vaclav Kotesovec, Jul 02 2014
a(n) = Sum_{s=0..n-1} binomial(n,s)*(-1)^s*A092477(n,n-s), n > 0. - R. J. Mathar, Nov 18 2023

A287274 Array read by antidiagonals: T(m,n) = number of dominating sets in the lattice (rook) graph K_m X K_n.

Original entry on oeis.org

1, 3, 3, 7, 11, 7, 15, 51, 51, 15, 31, 227, 421, 227, 31, 63, 963, 3615, 3615, 963, 63, 127, 3971, 30517, 59747, 30517, 3971, 127, 255, 16131, 252231, 989295, 989295, 252231, 16131, 255, 511, 65027, 2054941, 16219187, 32260381, 16219187, 2054941, 65027, 511

Offset: 1

Andrew Howroyd, May 22 2017

A set of vertices can be represented as an m X n binary matrix. If all rows contain at least one 1 then regardless of what is in each row the set will form a dominating set giving (2^n-1)^m solutions. Otherwise if only iA183109(i,n) solutions.

			Array begins:
=============================================================================
m\n|   1     2       3         4           5             6               7
---|-------------------------------------------------------------------------
1  |   1     3       7        15          31            63             127...
2  |   3    11      51       227         963          3971           16131...
3  |   7    51     421      3615       30517        252231         2054941...
4  |  15   227    3615     59747      989295      16219187       263425695...
5  |  31   963   30517    989295    32260381    1048220463     33884452717...
6  |  63  3971  252231  16219187  1048220463   67680006971   4358402146791...
7  | 127 16131 2054941 263425695 33884452717 4358402146791 559876911043381...
...

Andrew Howroyd, Table of n, a(n) for n = 1..780
Stephan Mertens, Domination Polynomial of the Rook Graph, JIS 27 (2024) 24.3.7; arXiv:2401.00716 [math.CO], 2024.
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal is A287065.
Row 2 is A191341.
Cf. A183109, A088699 (independent vertex sets), A290632.

b[m_, n_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}];
a[m_, n_] := (2^n - 1)^m + Sum[ b[i, n]*Binomial[m, i], {i, 1, m - 1}];
Table[a[m - n + 1, n], {m, 1, 9}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jun 12 2017, adapted from PARI *)

b(m,n)=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
a(m,n)=(2^n-1)^m + sum(i=1,m-1,b(i,n)*binomial(m,i));
for (i=1,7,for(j=1,7, print1(a(i,j), ",")); print);

T(m, n) = (2^n-1)^m + Sum_{i=1..m-1} binomial(m,i) * A183109(i,n).

A173403 Inverse binomial transform of A002416.

Original entry on oeis.org

1, 1, 13, 469, 63577, 33231721, 68519123173, 562469619451069, 18442242396353040817, 2417685638793025070212561, 1267626422541873052658376446653, 2658442047546208031914776455678477989, 22300713297142388711251601783864453690641417

Offset: 0

Brian Drake, Feb 17 2010

nonn

a(n) is the number of n X n matrices of 0's and 1's with the property that there is no index k such that both the k-th column and the k-th row consist of all zeros.

a(n) is the number of binary relations on n labeled vertices with no vertex of indegree and outdegree = 0. - Geoffrey Critzer, Oct 02 2012

E. A. Bender and S. G. Williamson, Foundations of Combinatorics with Applications, Dover, 2005, exercise 4.1.6.

Brian Drake, Table of n, a(n) for n = 0..50

Cf. A002416, A135748, A287065, A048291.

N:=8: seq( sum(binomial(n,i)*2^((n-i)^2)*(-1)^(i), i=0..n), n=0..N);

Table[Sum[(-1)^k Binomial[n,k] 2^(n-k)^2,{k,0,n}],{n,0,20}]  (* Geoffrey Critzer, Oct 02 2012 *)

a(n) = Sum_{k=0..n} (-1)^k*binomial(n,k)*2^((n-k)^2).

a(n) ~ 2^(n^2). - Vaclav Kotesovec, Oct 30 2017

A303208 Number of total dominating sets in the n X n rook graph.

Original entry on oeis.org

0, 9, 334, 53731, 30844786, 66544564805, 556588617042914, 18376877842518517955, 2414913046805958120844234, 1267171440764716263069641387581, 2658150749788131925244338204731596650, 22299981643440069703358952237798936248817875

Offset: 1

Eric W. Weisstein, Apr 19 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Rook Graph
Eric Weisstein's World of Mathematics, Total Dominating Set

Main diagonal of A384116.

Cf. A287065, A289196, A303211, A347921.

b[0] = 1; b[n_] := (2^n - 1)^n + Sum[Binomial[n, i] Sum[(-1)^j (-1 + 2^(n - j))^i Binomial[n, j], {j, 0, n}], {i, n - 1}]; Table[Sum[(-1)^k Binomial[n, k]^2 k! b[n - k], {k, 0, n}], {n, 10}]

\\ here c(n) is A287065.
b(m, n)=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
c(n)=(2^n-1)^n + sum(i=1, n-1, b(n, i)*binomial(n, i));
a(n) = {sum(k=0, n, (-1)^k*binomial(n,k)^2*k!*c(n-k))} \\ Andrew Howroyd, Apr 20 2018

a(n) = Sum_{k=0..n} (-1)^k*binomial(n,k)^2*k!*A287065(n-k). - Andrew Howroyd, Apr 20 2018

a(n) ~ 2^(n^2). - Vaclav Kotesovec, Apr 20 2018

Terms a(6) and beyond from Andrew Howroyd, Apr 20 2018

A289196 Number of connected dominating sets in the n X n rook graph.

Original entry on oeis.org

1, 9, 325, 51465, 30331861, 66273667449, 556170787050565, 18374555799096912585, 2414861959450912233421141, 1267166974391002542218440851129, 2658149210218078451926703769353958085, 22299979556058598891936157095746389850916425

Offset: 1

Eric W. Weisstein, Jun 28 2017

nonn

A set of vertices in the n X n rook graph can be represented as a n X n binary matrix. The vertex set will be dominating if either every row contains a 1 or every column contains a 1. - Andrew Howroyd, Jul 18 2017

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal of A360875.

Cf. A183109, A262307, A286189, A287065.

(* b = A183109, T = A262307 *) b[m_, n_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}]; T[, 1] = T[1, ] = 1; T[m_, n_] := T[m, n] = b[m, n] - Sum[T[i, j]*b[m-i, n-j]*Binomial[m-1, i-1]*Binomial[n, j], {i, 1, m-1}, {j, 1, n-1}]; a[n_] := T[n, n] + 2*Sum[ Binomial[n, k]*T[n, k], {k, 1, n-1}]; Array[a, 12] (* Jean-François Alcover, Oct 02 2017, after Andrew Howroyd *)

G(N)={S=matrix(N, N); T=matrix(N, N); U=matrix(N, N);
\\ S is A183109, T is A262307, U is m X n variant of this sequence.
for(m=1, N, for(n=1, N,
S[m, n]=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
T[m, n]=S[m, n]-sum(i=1, m-1, sum(j=1, n-1, T[i, j]*S[m-i, n-j]*binomial(m-1, i-1)*binomial(n, j)));
U[m, n]=sum(i=1, m, binomial(m, i)*T[i, n])+sum(j=1, n, binomial(n,j)*T[m, j])-T[m,n] )); U}
a(n)=G(n)[n, n]; \\ Andrew Howroyd, Jul 18 2017

a(n) = A262307(n,n) + 2*Sum_{k=1..n-1} binomial(n,k) * A262307(n,k). - Andrew Howroyd, Jul 18 2017

Terms a(6) and beyond from Andrew Howroyd, Jul 18 2017

A368831 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the n X n rook graph (n >= 0, 0 <= k <= n^2).

Original entry on oeis.org

1, 0, 1, 0, 0, 6, 4, 1, 0, 0, 0, 48, 117, 126, 84, 36, 9, 1, 0, 0, 0, 0, 488, 2640, 6712, 10864, 12726, 11424, 8008, 4368, 1820, 560, 120, 16, 1, 0, 0, 0, 0, 0, 6130, 58300, 269500, 808325, 1778875, 3075160, 4349400, 5154900, 5186300, 4454400, 3268360, 2042950, 1081575, 480700, 177100, 53130, 12650, 2300, 300, 25, 1

Offset: 0

Stephan Mertens, Jan 07 2024

The entries in row n are the coefficients of the domination polynomial of the n X n rook graph.
Sum of entries in row n = A287065 = main diagonal of A287274.
Number of minimum dominating sets T(n,n) = A248744(n).

			Triangle begins: (first 5 rows)
  1;
  0, 1;
  0, 0, 6,  4,   1;
  0, 0, 0, 48, 117,  126,   84,    36,     9,     1;
  0, 0, 0,  0, 488, 2640, 6712, 10864, 12726, 11424, 8008, 4368, 1820, 560, 120, 16, 1;
  ...

John J. Watkins, Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, 2004, chapter 7.

Alois P. Heinz, Rows n = 0..32, flattened
Stephan Mertens, Domination Polynomial of the Rook Graph, Journal of Integer Sequences 27 (2024), Article 24.3.7; arXiv:2401.00716 [math.CO], 2024.
Eric Weisstein's World of Mathematics, Dominating Set.
Eric Weisstein's World of Mathematics, Rook Graph.

Cf. A000290, A083374, A287065 (row sums), A287274, A248744 (leading diagonal).

R[n_, m_] := CoefficientList[((x + 1)^n - 1)^m - (-1)^m*Sum[Binomial[m, k]*(-1)^k*((1 + x)^k - 1)^n, {k, 0, m - 1}], x];
Flatten[Table[R[n,n],{n,1,5}]]

G.f.: ((x+1)^n - 1)^m - (-1)^m * Sum_{k=0..m-1} binomial(m,k)*(-1)^k*((1+x)^k - 1)^n (for the rectangular n X m rook graph).

T(n,n) = 2*n^n - n!.

cp's OEIS Frontend

A048291 Number of {0,1} n X n matrices with no zero rows or columns.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A287274 Array read by antidiagonals: T(m,n) = number of dominating sets in the lattice (rook) graph K_m X K_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A173403 Inverse binomial transform of A002416.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A303208 Number of total dominating sets in the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A289196 Number of connected dominating sets in the n X n rook graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A368831 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the n X n rook graph (n >= 0, 0 <= k <= n^2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula