A392486 Number of n X n Boolean matrices having at least one zero row and at least one zero column.

1, 5, 91, 5789, 1294051, 1039469765, 3073042377931, 34139630997602429, 1448619811273434076291, 237593684317356351961920965, 151899424140037314618300037972171, 380770342284956379526110819270063394589, 3757810450724244615026582012010234761604306211, 146432166092518833922193666738447590805307079982745605

Offset

1,2

Comments

a(n) is the number of n X n matrices that neither row-consistent nor column-consistent (equivalently, has at least one column of zeros and at least one row of zeros).

Links

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

R. Duncan Luce, A Note on Boolean Matrix Theory, Proceedings of the American Mathematical Society 3 (1952), 382-388.

Formula

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

Example

For n = 3, a(3) = 91 is the total number of 3 X 3 Boolean matrices with at least one column of zeros and one row of zeros.

Mathematica

a[n_Integer?NonNegative] := Sum[Sum[(-1)^(i + j) Binomial[n, i] Binomial[n, j] 2^((n - i) (n - j)), {j, 1, n}], {i, 1, n}];
seq[n_Integer?NonNegative] := Table[a[k], {k, 1, n}]

Crossrefs

Cf. A048291, A392485. Row sums of triangle A392483.

Sequence in context: A343009 A368776 A340052 * A340883 A109625 A266290

Adjacent sequences: A392483 A392484 A392485 * A392487 A392488 A392489

Keyword

nonn

Author

Courtney Gibbons, Jan 21 2026

Status

approved