cp's OEIS Frontend

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.

%I A350189 #68 Jun 10 2024 08:50:49
%S A350189 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,
%T A350189 140,296,500,780,1005,1085,992,560,170,1,6,30,110,330,876,1956,4020,
%U A350189 7140,11480,16248,19608,20560,16500,9720,3276,360,1,7,42,182,665,2121,5852,14792,33117,68355,126994,214158
%N 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.
%C A350189 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.
%C A350189 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.]
%C A350189 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.
%H A350189 Max Alekseyev, <a href="/A350189/b350189.txt">Table of n, a(n) for n = 0..361</a> (rows 0..14; rows 0..9 from R. J. Mathar)
%H A350189 P. Erdos and D. Kleitman, <a href="https://doi.org/10.1090/S0002-9939-1971-0270924-9">On collections of subsets containing no 4-member boolean algebra</a>, Proc. Am. Math. Soc. 28 (1) (1971) 87.
%H A350189 R. J. Mathar, <a href="/A350189/a350189.pdf">Illustration of graphs with these incidence matrices</a>
%H A350189 <a href="/index/Mat#binmat">Index entries for sequences of binary matrices</a>
%H A350189 <a href="/index/Sq#square_free">Index entries for sequences of squarefree graphs</a>
%F A350189 T(n,0) = 1.
%F A350189 T(n,1) = n.
%F A350189 T(n,2) = A002378(n-1).
%F A350189 T(n,3) = A006331(n-1).
%F A350189 T(n,4) = n*(n-1)*(n-2)*(5*n+3)/12 = A147875(n)*A000217(n-1)/3. - _R. J. Mathar_, Mar 10 2022
%F A350189 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
%F A350189 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
%F A350189 Conjecture: the largest k such that T(n,k) is nonzero is k = A072567(n) = A001197(n) - 1. - _Max Alekseyev_, Apr 03 2022
%e A350189 The triangle starts
%e A350189   1;
%e A350189   1 1;
%e A350189   1 2 2 2;
%e A350189   1 3 6 10 9 9 4;
%e A350189   1 4 12 28 46 72 80 80 60 16;
%e A350189   1 5 20 60 140 296 500 780 1005 1085 992 560 170;
%e A350189   ...
%e A350189 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
%Y A350189 Cf. A001197 (conjectured row lengths), A352258 (row sums), A352801 (rightmost terms), A350296, A350304, A350237, A352472 (traceless symmetric).
%Y A350189 Cf. A002378, A006331, A000217, A147875.
%K A350189 nonn,tabf
%O A350189 0,5
%A A350189 _R. J. Mathar_, Mar 09 2022