cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 11-20 of 25 results. Next

A006617 Zarankiewicz's problem.

Original entry on oeis.org

6, 10, 14, 19, 25, 30, 36, 43, 51, 57
Offset: 2

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all ones 2 X 3 submatrix. - Sean A. Irvine, May 17 2017

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

A006618 Zarankiewicz's problem.

Original entry on oeis.org

11, 17, 22, 28, 36, 43, 51, 61
Offset: 3

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all ones 2 X 4 submatrix. - Sean A. Irvine, May 18 2017

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

A006619 Zarankiewicz's problem.

Original entry on oeis.org

8, 13, 18, 24, 31, 38, 46, 55
Offset: 2

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the least k such that every n X (n+2) {0,1}-matrix with k ones contains an all ones 2 X 4 submatrix. - Sean A. Irvine, May 18 2017

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

A347472 Maximum number of nonzero entries allowed in an n X n matrix to ensure there is a 2 X 2 zero submatrix.

Original entry on oeis.org

0, 2, 6, 12, 19, 27, 39, 51, 65, 81, 98, 116, 139, 163, 188, 214, 242, 272, 303, 335, 375, 413, 453
Offset: 2

Views

Author

M. F. Hasler, Sep 28 2021

Keywords

Comments

Related to Zarankiewicz's problem k_2(n) (cf. A001197 and other crossrefs) which asks the converse: how many 1's must be in an n X n {0,1}-matrix in order to guarantee the existence of an all-ones 2 X 2 submatrix. This complementarity leads to the given formula which was used to compute the given values.
See A347473 and A347474 for the similar problem with a 3 X 3 resp. 4 X 4 zero submatrix.

Examples

			For n = 2, there must not be any nonzero entry in an n X n = 2 X 2 matrix, if one wants a 2 X 2 zero submatrix, whence a(2) = 0.
For n = 3, having at most 2 nonzero entries in the n X n matrix still guarantees that there is a 2 X 2 zero submatrix (delete the row of the first nonzero entry and then the column of the remaining nonzero entry, if any), but if one allows 3 nonzero entries and they are placed on the diagonal, then there is no 2 X 2 zero submatrix. Hence, a(3) = 2.

Crossrefs

Cf. A001197 (k_2(n)), A001198 (k_3(n)), A006613 - A006626.
Cf. A347473, A347474 (analog for 3 X 3 resp. 4 X 4 zero submatrix).
Cf. A350296.

Formula

a(n) = n^2 - A001197(n).
a(n) = A350296(n) - 1. - Andrew Howroyd, Dec 23 2021

Extensions

a(22)-a(24) computed from A001197 by Max Alekseyev, Feb 08 2022

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.

Original entry on oeis.org

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

Views

Author

R. J. Mathar, Mar 09 2022

Keywords

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

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

A350296 Minimum number of 1's in an n X n binary matrix with no zero 2 X 2 submatrix.

Original entry on oeis.org

0, 1, 3, 7, 13, 20, 28, 40, 52, 66, 82, 99, 117, 140, 164, 189, 215, 243, 273, 304, 336, 376, 414, 454
Offset: 1

Views

Author

Andrew Howroyd, Dec 23 2021

Keywords

Examples

			Solutions for a(3)=3, a(4)=7, a(5)=13, a(6)=20:
  . . x    . . . x    . . . . x    . . . x x x
  . x .    . x x .    . x x x .    . x x . . x
  x . .    x . x .    x . x x .    x . x . x .
           x x . .    x x . x .    x x . x . .
                      x x x . .    . x x x x .
                                   x . x x . x

Crossrefs

Column 2 of A339635.
Cf. A001197, A072567, A152125, A227133, A347472.

Formula

a(n) = A347472(n) + 1 = n^2 - A001197(n) + 1 = n^2 - A072567(n).
a(n) >= A152125(n).

Extensions

a(22)-a(24) computed from A001197, added by Max Alekseyev, Feb 08 2022

A001843 The coding-theoretic function A(n,4,4).

Original entry on oeis.org

1, 1, 3, 7, 14, 18, 30, 35, 51, 65, 91, 105, 140, 157, 198, 228, 285, 315, 385, 419, 498, 550, 650, 702, 819, 877, 1005, 1085, 1240, 1320, 1496, 1583, 1773, 1887, 2109, 2223, 2470, 2593, 2856, 3010, 3311, 3465, 3795, 3959, 4308, 4508, 4900, 5100, 5525, 5737
Offset: 4

Views

Author

N. J. A. Sloane

Keywords

Comments

Maximal number of 4-subsets of an n-set such that any two subsets meet in at most 2 points.

Examples

			For n=7 use all seven cyclic shifts of 1110100.

References

  • CRC Handbook of Combinatorial Designs, 1996, p. 411.
  • R. K. Guy, A problem of Zarankiewicz, in P. ErdÅ‘s and G. Katona, editors, Theory of Graphs (Proceedings of the Colloquium, Tihany, Hungary), Academic Press, NY, 1968, pp. 119-150.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Programs

  • Maple
    A001843 :=  proc(n)
    floor((n-1)/3* floor((n-2)/2) ) ;
    if modp(n,6) = 0 then
        floor(n*(%-1)/4) ;
    else
        floor(n*%/4) ;
    end if;
end proc:
seq(A001843(n),n=4..80) ; # R. J. Mathar, Oct 01 2021
  • Python
    [((n-2)//2*(n-1)//3 - int(n%6 == 0)) * n // 4 for n in range(4, 50)]
# Andrey Zabolotskiy, Jan 28 2021

Formula

See Theorem 1.2 of Bao and Ji, 2015 (Theorem 4.9 in the arXiv preprint, but note the missing parentheses for J(n,4,4) on page 1).
a(n)= +a(n-1) +a(n-2) -a(n-3) +a(n-6) -a(n-7) -a(n-8) +a(n-9) +a(n-12) -a(n-13) -a(n-14) +a(n-15) -a(n-18) +a(n-19) +a(n-20) -a(n-21). - R. J. Mathar, Oct 01 2021

Extensions

Revised by N. J. A. Sloane and Andries E. Brouwer, May 08 2010
Terms a(23) and beyond added, entry edited by Andrey Zabolotskiy, Jan 28 2021

A006614 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all-ones 2 X 4 submatrix.

Original entry on oeis.org

14, 21, 26, 32, 41, 48, 56, 67
Offset: 4

Views

Author

N. J. A. Sloane

Keywords

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A006613, A006615, A006616, A006617, A006618, A006619, A006620, A006621, A006622, A006623, A006624, A006625, A006626.
Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Extensions

Name updated at the suggestion of Sean A. Irvine by Max Alekseyev, Feb 02 2024

A006615 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.

Original entry on oeis.org

15, 22, 31, 38, 46, 57
Offset: 4

Views

Author

N. J. A. Sloane

Keywords

References

  • R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Crossrefs

Cf. A006613, A006614, A006616, A006617, A006618, A006619, A006620, A006621, A006622, A006623, A006624, A006625, A006626.
Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Extensions

Name changed at the suggestion of Sean A. Irvine and a(9) added by Max Alekseyev, Feb 02 2024

A006622 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.

Original entry on oeis.org

12, 18, 26, 33, 41, 51
Offset: 3

Views

Author

N. J. A. Sloane

Keywords

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A006613, A006614, A006615, A006616, A006617, A006618, A006619, A006620, A006621, A006623, A006624, A006625, A006626.
Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Extensions

Name edited at the suggestion of Sean A. Irvine and a(8) added by Max Alekseyev, Feb 02 2024
Previous Showing 11-20 of 25 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.