|
|
A354741
|
|
Triangular array read by rows. T(n,k) is the number of n X n Boolean matrices with row rank k, n >= 0, 0 <= k <= n.
|
|
2
|
|
|
1, 1, 1, 1, 9, 6, 1, 49, 306, 156, 1, 225, 8550, 37488, 19272, 1, 961, 194850, 4811700, 17551800, 10995120
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Compare to A286331 which counts n X n matrices over the field GF(2). Note that the limit when n->oo of the probability that a matrix over GF(2) has rank n is equal to Product_{i>=1} (1-1/2^i) = 0.288... (see A048651). Here, it appears (from some empirical computations) that the limiting probability that a Boolean matrix has rank n is 1.
|
|
LINKS
|
|
|
FORMULA
|
T(n,0) = 1.
T(n,1) = (2^n-1)^2.
T(n,2) = (3^n - 2*2^n + 1)^2 + (1/2)*(4^n - 2*3^n + 2^n)^2.
|
|
EXAMPLE
|
Table begins:
1;
1, 1;
1, 9, 6;
1, 49, 306, 156;
1, 225, 8550, 37488, 19272;
...
|
|
MATHEMATICA
|
Table[B = Tuples[Tuples[{0, 1}, nn], nn]; bospan[matrix_]:= Sort[DeleteDuplicates[
Map[Clip[Total[#]] &, Drop[Subsets[matrix], 1]]]]; rowrank[matrix_] :=
If[Total[Map[Total, matrix]] == 0, 0, Length[Select[Drop[Subsets[DeleteCases[matrix, Table[0, {nn}]]], 1],
bospan[#] == bospan[DeleteCases[matrix, Table[0, {nn}]]] &][[ 1]]]]; Tally[
Table[rowrank[B[[i]]], {i, 1, 2^(nn^2)}]][[All, 2]], {nn, 0, 4}] // Grid
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|