A173403 -id:A173403 - 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

A287065 Number of dominating sets on the n X n rook graph.

Original entry on oeis.org

1, 11, 421, 59747, 32260381, 67680006971, 559876911043381, 18412604442711949187, 2416403019417984915336061, 1267413006543912045144741284411, 2658304092145691708492995820522716981, 22300364428188338185156192161829091442585827

Offset: 1

Eric W. Weisstein, May 19 2017

nonn

Number of {0,1} n X n matrices with no zero rows or no zero columns. - Geoffrey Critzer, Jan 15 2024

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

Main diagonal of A287274.
Row sums of A368831.
Cf. A183109, A002720, A048291, A173403.

Table[(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}], {n, 20}] (* Eric W. Weisstein, May 27 2017 *)

b(m,n)=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
a(n)=(2^n-1)^n + sum(i=1,n-1,b(n,i)*binomial(n,i)); \\ Andrew Howroyd, May 22 2017

a(n) = (2^n-1)^n + Sum_{i=1..n-1} binomial(n,i) * A183109(n,i). - Andrew Howroyd, May 22 2017

a(6)-a(12) from Andrew Howroyd, May 22 2017

A173505 Triangle T(n, k, q) = c(n, q)/(c(k, q)*c(n-k, q)) where c(n,q) = Product_{j=1..n} (q^j -1)^(n-j) and q = 4, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 45, 45, 1, 1, 2835, 42525, 2835, 1, 1, 722925, 683164125, 683164125, 722925, 1, 1, 739552275, 178213609468125, 11227457396491875, 178213609468125, 739552275, 1, 1, 3028466566125, 746569779579727228125, 11993643508948317919828125, 11993643508948317919828125, 746569779579727228125, 3028466566125, 1

Offset: 0

Roger L. Bagula, Feb 20 2010

			The triangle begins as:
  1;
  1,         1;
  1,         3,               1;
  1,        45,              45,                 1;
  1,      2835,           42525,              2835,               1;
  1,    722925,       683164125,         683164125,          722925,         1;
  1, 739552275, 178213609468125, 11227457396491875, 178213609468125, 739552275, 1;

G. C. Greubel, Rows n = 0..23 of the triangle, flattened

Cf. A173403, A173404.

c[n_, q_]:= Product[(q^m-1)^(n-m), {m,1,n}];
T[n_, k_, q_]:= c[n, q]/(c[k, q]*c[n-k, q]);
Table[T[n, k, 4], {n,0,10}, {k,0,n}]//Flatten (* modified by G. C. Greubel, Apr 25 2021 *)

@CachedFunction
def c(n,q): return product( (q^j -1)^(n-j) for j in (1..n))
def T(n,k,q): return c(n,q)/(c(k,q)*c(n-k,q))
flatten([[T(n,k,4) for k in (0..n)] for n in (0..10)]) # G. C. Greubel, Apr 25 2021

q=4;c(n,q)=Product[(q^m - 1)^(n - m), {m, 1, n}];

t(n,k,q)=c(n, q)/(c(k, q)*c(n - k, q))

Edited by G. C. Greubel, Apr 25 2021

A217436 Triangular array read by rows. T(n,k) is the number of labeled relations on n elements with exactly k vertices of indegree and outdegree = 0.

Original entry on oeis.org

1, 1, 1, 13, 2, 1, 469, 39, 3, 1, 63577, 1876, 78, 4, 1, 33231721, 317885, 4690, 130, 5, 1, 68519123173, 199390326, 953655, 9380, 195, 6, 1, 562469619451069, 479633862211, 697866141, 2225195, 16415, 273, 7, 1, 18442242396353040817, 4499756955608552, 1918535448844, 1860976376, 4450390, 26264, 364, 8, 1

Offset: 0

Geoffrey Critzer, Oct 02 2012

Row sums = 2^(n^2). First column (k = 0) is A173403.

Sum_{k=1,2,...,n} T(n,k)*k = A197927.

			1,
1, 1,
13, 2, 1,
469, 39, 3, 1,
63577, 1876, 78, 4, 1,
33231721, 317885, 4690, 130, 5, 1,
68519123173, 199390326, 953655, 9380, 195, 6, 1

nn=6; s=Sum[Sum[(-1)^k Binomial[n,k] 2^(n-k)^2, {k,0,n}] x^n/n!, {n,0,nn}]; Range[0,nn]! CoefficientList[Series[Exp[ y x] s, {x,0,nn}], {x,y}] //Grid

E.g.f.: exp(y*x)*A(x) where A(x) is the e.g.f. for A173403.

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

A287065 Number of dominating sets on the n X n rook graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A173505 Triangle T(n, k, q) = c(n, q)/(c(k, q)*c(n-k, q)) where c(n,q) = Product_{j=1..n} (q^j -1)^(n-j) and q = 4, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A217436 Triangular array read by rows. T(n,k) is the number of labeled relations on n elements with exactly k vertices of indegree and outdegree = 0.

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Formula