A350189 Triangle T(n,k) read by rows: the number of symmetric binary n X n matrices with k ones and no all-1 2 X 2 submatrix.

1, 1, 1, 1, 2, 2, 2, 1, 3, 6, 10, 9, 9, 4, 1, 4, 12, 28, 46, 72, 80, 80, 60, 16, 1, 5, 20, 60, 140, 296, 500, 780, 1005, 1085, 992, 560, 170, 1, 6, 30, 110, 330, 876, 1956, 4020, 7140, 11480, 16248, 19608, 20560, 16500, 9720, 3276, 360, 1, 7, 42, 182, 665, 2121, 5852, 14792, 33117, 68355, 126994, 214158

Offset: 0

Author

R. J. Mathar, Mar 09 2022

Keywords

• nonn
• tabf

Comments

There are 2^(n^2) binary n X n matrices (entries of {0,1}). There are 2^(n*(n+1)/2) symmetric binary matrices. There are A184948(n,k) symmetric binary n X n matrices with k ones.

This sequence is the triangle T(n,k) of symmetric binary n x n matrices with k ones but no 2 X 2 submatrix with all entries = 1. [So in the display of these matrices there is no rectangle with four 1's at the corners.]

The row lengths minus 1 are 0, 1, 3, 6, 9, 12, 17, 21, 24, 29, ... and indicate the maximum number of 1's than can be packed into a symmetric binary n X n matrix without creating an all-1 quadrangle/submatrix of order 2.

Examples

			The triangle starts
  1;
  1 1;
  1 2 2 2;
  1 3 6 10 9 9 4;
  1 4 12 28 46 72 80 80 60 16;
  1 5 20 60 140 296 500 780 1005 1085 992 560 170;
  ...
To place 4 ones, one can place 2 of them in C(n,2) ways on the diagonal and the other 2 in n*(n-1)/2 ways outside the diagonal, avoiding one matrix that builds an all-1 submatrix, which are C(n,2)*(n*(n-1)/2-1) matrices. One can place all 4 on the diagonal in C(n,4) ways. One can place 2 outside the diagonal (the other 2 mirror symmetrically) in C(n*(n-1)/2,2) ways. Sum of the 3 terms is T(n,4) = C(n,3)*(5*n+3)/2. - _R. J. Mathar_, Mar 10 2022
		

Links

• Max Alekseyev, Table of n, a(n) for n = 0..361 (rows 0..14; rows 0..9 from R. J. Mathar)
• P. Erdos and D. Kleitman, On collections of subsets containing no 4-member boolean algebra, Proc. Am. Math. Soc. 28 (1) (1971) 87.
• R. J. Mathar, Illustration of graphs with these incidence matrices
• Index entries for sequences of binary matrices
• Index entries for sequences of squarefree graphs

Crossrefs

Cf. A001197 (conjectured row lengths), A352258 (row sums), A352801 (rightmost terms), A350296, A350304, A350237, A352472 (traceless symmetric).

Cf. A002378, A006331, A000217, A147875.

Formula

T(n,0) = 1.

T(n,1) = n.

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

T(n,3) = A006331(n-1).

T(n,4) = n*(n-1)*(n-2)*(5*n+3)/12 = A147875(n)*A000217(n-1)/3. - R. J. Mathar, Mar 10 2022

T(n,5) = n*(n-1)*(n-2)*(13*n^2-n-24)/60. T(n,6) = n*(n-1)*(n-2)*(19*n^3-18*n^2-97*n+60)/180. T(n,7) = n*(n-1)*(n-2)*(n-3)*(58*n^3+75*n^2-223*n+180)/1260. - Conjectured by R. J. Mathar, Mar 11 2022; proved by Max Alekseyev, Apr 02 2022

G.f.: F(x,y) = Sum_{n,k} T(n,k)*x^n/n!*y^k = exp( Sum_G x^n(G) * y^u(G) / |Aut(G)| ), where G runs over the connected squarefree graphs with loops, n(G) is the number of nodes in G, u(G) the number of ones in the adjacency matrix of G, and Aut(G) is the automorphism group of G. It follows that F(x,y) = exp(x) * (1 + x*y + x^2*y^2 + (2/3*x^3 + x^2)*y^3 + (5/12*x^4 + 3/2*x^3)*y^4 + (13/60*x^5 + 3/2*x^4 + 3/2*x^3)*y^5 + (19/180*x^6 + 7/6*x^5 + 8/3*x^4 + 2/3*x^3)*y^6 + (29/630*x^7 + 3/4*x^6 + 19/6*x^5 + 10/3*x^4)*y^7 + O(y^8)), implying the above formulas for T(n,k). - Max Alekseyev, Apr 02 2022

Conjecture: the largest k such that T(n,k) is nonzero is k = A072567(n) = A001197(n) - 1. - Max Alekseyev, Apr 03 2022