login
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.
6
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
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
KEYWORD
nonn,tabf
AUTHOR
Vladeta Jovovic, Jun 01 2000
STATUS
approved