A355333 -id:A355333 - cp's OEIS frontend

A355334 Triangle read by rows: T(n,k) is the number of unlabeled graphs with n nodes and bipartite dimension (or biclique covering number) k, 0 <= k < n.

1, 1, 1, 1, 2, 1, 1, 4, 6, 0, 1, 6, 20, 7, 0, 1, 9, 61, 80, 5, 0, 1, 12, 159, 650, 221, 1, 0, 1, 16, 381, 4710, 6866, 372, 0, 0, 1, 20, 832, 29921, 183618, 59950, 326, 0, 0

Offset: 1

Pontus von Brömssen, Jun 29 2022

			Triangle begins:
  n\k | 0  1   2     3      4     5   6  7  8
  ----+--------------------------------------
   1  | 1
   2  | 1  1
   3  | 1  2   1
   4  | 1  4   6     0
   5  | 1  6  20     7      0
   6  | 1  9  61    80      5     0
   7  | 1 12 159   650    221     1   0
   8  | 1 16 381  4710   6866   372   0  0
   9  | 1 20 832 29921 183618 59950 326  0  0

Wikipedia, Bipartite dimension

Cf. A000088 (row sums), A355333, A355335, A355336.

Columns: A000012 (k=0), A002620 (k=1).

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.

Original entry on oeis.org

1, 1, 1, 1, 9, 6, 1, 49, 306, 156, 1, 225, 8550, 37488, 19272, 1, 961, 194850, 4811700, 17551800, 10995120

Offset: 0

Geoffrey Critzer, Jun 12 2022

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.

			Table begins:
  1;
  1,   1;
  1,   9,    6;
  1,  49,  306,   156;
  1, 225, 8550, 37488, 19272;
  ...

Wikipedia, Boolean matrix

Columns k = 0 and 1 give A000012, A060867.
Row sums give A002416.
Cf. A048651, A064230, A286331, A355333.

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

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.

Row n=5 from Pontus von Brömssen, Jul 14 2022

cp's OEIS Frontend

A355334 Triangle read by rows: T(n,k) is the number of unlabeled graphs with n nodes and bipartite dimension (or biclique covering number) k, 0 <= k < n.

Views

Author

Keywords

Examples

Links

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions