cp's OEIS Frontend

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.

%I A055599 #44 Feb 16 2025 08:32:43
%S A055599 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,
%T A055599 9696,7480,4272,1812,560,120,16,1,0,0,0,0,0,120,4200,43000,222925,
%U A055599 727375,1674840,2913100,3995100,4441200,4073100,3114140,1994550
%N 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.
%C A055599 Rows also give the coefficients of the edge cover polynomials of the complete bipartite graph K_{n,n}. - _Eric W. Weisstein_, Apr 24 2017
%H A055599 H. Cheballah, S. Giraudo, and R. Maurice, <a href="http://arxiv.org/abs/1306.6605">Combinatorial Hopf algebra structure on packed square matrices</a>, arXiv preprint arXiv:1306.6605 [math.CO], 2013.
%H A055599 Stephan Mertens, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Mertens/mertens6.html">Domination Polynomial of the Rook Graph</a>, JIS 27 (2024) 24.3.7; <a href="https://arxiv.org/abs/2401.00716">arXiv:2401.00716</a> [math.CO], 2024.
%H A055599 Roberto Tauraso, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Tauraso/tauraso18.html">Edge cover time for regular graphs</a>, JIS 11 (2008) 08.4.4
%H A055599 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>
%H A055599 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/EdgeCoverPolynomial.html">Edge Cover Polynomial</a>
%F A055599 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).
%F A055599 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
%F A055599 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
%e A055599 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].
%e A055599 Triangle begins:
%e A055599 0, 1,
%e A055599 0, 0, 2, 4, 1,
%e A055599 0, 0, 0, 6, 45, 90, 78, 36, 9, 1,
%e A055599 0, 0, 0, 0, 24, 432, 2248, 5776, 9066, 9696, 7480, 4272, 1812, 560, 120, 16, 1,
%e A055599 ...
%t A055599 row[n_] := Sum[(-1)^(n-k) Binomial[n, k] ((1+x)^k - 1)^n, {k, 0, n}] + O[x]^(n^2+1) // CoefficientList[#, x]&;
%t A055599 Table[row[n], {n, 1, 5}] // Flatten (* _Jean-François Alcover_, Nov 06 2018 *)
%Y A055599 Cf. A048291 (row sums).
%K A055599 nonn,tabf
%O A055599 1,5
%A A055599 _Vladeta Jovovic_, Jun 01 2000