A362943 Irregular triangular array read by rows. T(n,k) is the number of n X n Boolean relation matrices whose row span is k, n >= 0, 1 <= k <= 2^n.

1, 1, 1, 1, 9, 4, 2, 1, 49, 144, 198, 78, 36, 0, 6, 1, 225, 2500, 9650, 15864, 17640, 8784, 6936, 2304, 1320, 0, 288, 0, 0, 0, 24

Offset

0,5

Comments

Here, row span means the cardinality of the row space.

Links

Table of n, a(n) for n=0..30.

M. Breen and D Hume, On the cardinalities of row spaces of Boolean matrices, Technical Report, no. 1999-3, Tennessee Technological University.

Formula

T(n,1) = 1 (the zero matrix).

T(n,2^n) = n! (the permutation matrices).

T(n,2) = (2^n-1)^2.

For k > 2^(n-1), T(n,k) is nonzero iff k=2^(n-1)+2^j for any j in {0,1,2,...,n-1}.

Example

Triangle begins:
 1;
 1,   1;
 1,   9,    4,    2;
 1,  49,  144,  198,    78,    36,   0,     6;
 1, 225, 2500, 9650, 15864, 17640, 8784, 6936, 2304, 1320, 0, 288, 0, 0, 0, 24;
 ...
T(2,3)=4 because we have: {{0, 1}, {1, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}, {{1, 1}, {1, 0}}.

Mathematica

B[n_] := Tuples[Tuples[{0, 1}, n], n]; rowspace[matrix_, n_] := Sort[DeleteDuplicates[Clip[Tuples[{0, 1}, n].matrix]]]; Table[Table[
   Count[Map[Length[rowspace[#, n]] &, B[n]], k], {k, 1, 2^n}], {n, 0, 4}] // Grid

Crossrefs

Cf. A002416 (row sums), A060867 (column k=2).

Sequence in context: A248197 A199291 A091661 * A011313 A319530 A318410

Adjacent sequences: A362940 A362941 A362942 * A362944 A362945 A362946

Keyword

nonn,tabf,more

Author

Geoffrey Critzer, May 09 2023

Status

approved