A392483 Triangle read by rows, with T(n,k) giving the number of n X n Boolean matrices with exactly k ones having at least one zero row and at least one zero column.

1, 0, 1, 4, 0, 0, 0, 1, 9, 36, 36, 9, 0, 0, 0, 0, 0, 1, 16, 120, 560, 1332, 1728, 1296, 576, 144, 16, 0, 0, 0, 0, 0, 0, 0, 1, 25, 300, 2300, 12650, 47000, 118800, 211200, 273250, 264100, 193600, 108000, 45400, 14000, 3000, 400, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset

1,4

Comments

T(k,n) counts the number of n X n Boolean matrices with k ones that are neither row- nor column-consistent. The formula follows from inclusion-exclusion.

Links

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

R. Duncan Luce, A Note on Boolean Matrix Theory, Proc. Amer. Math. Soc. 3 (1952), 382--388.

Formula

T(n,k) = Sum_{i=1..n} Sum_{j=1..n} (-1)^(i+j) * binomial(n,i) * binomial(n,j) * binomial((n-i)*(n-j), k).

Example

For n = 2 and k = 1, the T(2,1) = 4 matrices are the 2 x 2 matrices with exactly one 1.
Triangle begins:
  1, 0
  1, 4, 0, 0, 0
  1, 9, 36, 36, 9, 0, 0, 0, 0, 0
  1, 16, 120, 560, 1332, 1728, 1296, 576, 144, 16, 0, 0, 0, 0, 0, 0, 0
  1, 25, 300, 2300, 12650, 47000, 118800, 211200, 273250, 264100, 193600, 108000, 45400, 14000, 3000, 400, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0
  ...

Mathematica

T[n_Integer?NonNegative, k_Integer?NonNegative] /; 0 <= k <= n^2 :=
  Module[{bn = Table[Binomial[n, t], {t, 0, n}]},
    -Sum[
      Sum[
        (-1)^(i + j) * bn[[i + 1]] * bn[[j + 1]] *
          Binomial[(n - i) (n - j), k],
        {j, 0, n}
      ],
      {i, 1, n}
    ]
  ];

Crossrefs

Cf. A055599, A392482, A392486 (row sums).

Sequence in context: A152894 A152898 A386636 * A368661 A369009 A345403

Adjacent sequences: A392480 A392481 A392482 * A392484 A392485 A392486

Keyword

nonn,tabf

Author

Courtney Gibbons, Jan 13 2026

Status

approved