A392485 Number of n X n Boolean matrices that are row-consistent but not column-consistent.

0, 2, 78, 9122, 3631230, 5156504762, 27001050877878, 534501094899058562, 40722145926117903423870, 12087546475818254213970440762, 14092107560516965761680288437626678, 64865786413692603712581708653173229695202, 1182842929982145786766341064087435441895201131230

Offset

1,2

Comments

a(n) is the number of n X n matrices that are row-consistent but not column-consistent (equivalently, has at least one column of zeros but no zero rows).

Links

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

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=0..n} (-1)^(i+j) * binomial(n,i) * binomial(n,j) * 2^((n-i)*(n-j)).

Example

For n = 3, a(3) = 78 is the total number of 3 X 3 Boolean matrices with at least one column of zeros but no zero rows.

Mathematica

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

Crossrefs

Cf. A048291, A392486.

Row sums of A392482.

Sequence in context: A157062 A008273 A231240 * A197101 A245674 A342979

Adjacent sequences: A392482 A392483 A392484 * A392486 A392487 A392488

Keyword

nonn

Author

Courtney Gibbons, Jan 14 2026

Status

approved