A055599 Triangle T(n,k) read by rows, giving the number of n X n binary matrices with no zero rows or columns and with k=0..n^2 ones.

0, 1, 0, 0, 2, 4, 1, 0, 0, 0, 6, 45, 90, 78, 36, 9, 1, 0, 0, 0, 0, 24, 432, 2248, 5776, 9066, 9696, 7480, 4272, 1812, 560, 120, 16, 1, 0, 0, 0, 0, 0, 120, 4200, 43000, 222925, 727375, 1674840, 2913100, 3995100, 4441200, 4073100, 3114140, 1994550

Offset

1,5

Comments

Rows also give the coefficients of the edge cover polynomials of the complete bipartite graph K_{n,n}. - Eric W. Weisstein, Apr 24 2017

Links

Table of n, a(n) for n=1..51.

H. Cheballah, S. Giraudo, and R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.

Stephan Mertens, Domination Polynomial of the Rook Graph, JIS 27 (2024) 24.3.7; arXiv:2401.00716 [math.CO], 2024.

Roberto 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 Polynomial

Formula

Number of m X n binary matrices with no zero rows or columns and with k=0..m*n ones is Sum_{i=0..n} (-1)^i*C(n, i)*a(m, n-i, k) where a(m, n, k)=Sum_{i=0..m} (-1)^i*C(m, i)*C((m-i)*n, k).

G.f. for n-th row: Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*((1+x)^k-1)^n. - Vladeta Jovovic, Apr 04 2003

E.g.f.: Sum(((1+y)^n-1)^n*exp((1-(1+y)^n)*x)*x^n/n!,n=0..infinity). - Vladeta Jovovic, Feb 24 2008

Example

For m=n=3 we get T(3,k)=C(9,k)-6*C(6,k)+9*C(4,k)+6*C(3,k)-18*C(2,k)+9*C(1,k)-C(0,k) giving the batch [0,0,0,6,45,90,78,36,9,1].
Triangle begins:
0, 1,
0, 0, 2, 4, 1,
0, 0, 0, 6, 45, 90, 78, 36, 9, 1,
0, 0, 0, 0, 24, 432, 2248, 5776, 9066, 9696, 7480, 4272, 1812, 560, 120, 16, 1,
...

Mathematica

row[n_] := Sum[(-1)^(n-k) Binomial[n, k] ((1+x)^k - 1)^n, {k, 0, n}] + O[x]^(n^2+1) // CoefficientList[#, x]&;
Table[row[n], {n, 1, 5}] // Flatten (* Jean-François Alcover, Nov 06 2018 *)

Crossrefs

Cf. A048291 (row sums).

Sequence in context: A366466 A365948 A365950 * A115407 A010586 A354499

Adjacent sequences: A055596 A055597 A055598 * A055600 A055601 A055602

Keyword

nonn,tabf

Author

Vladeta Jovovic, Jun 01 2000

Status

approved