A001197 -id:A001197 - cp's OEIS frontend

A001840 Expansion of g.f. x/((1 - x)^2*(1 - x^3)).

0, 1, 2, 3, 5, 7, 9, 12, 15, 18, 22, 26, 30, 35, 40, 45, 51, 57, 63, 70, 77, 84, 92, 100, 108, 117, 126, 135, 145, 155, 165, 176, 187, 198, 210, 222, 234, 247, 260, 273, 287, 301, 315, 330, 345, 360, 376, 392, 408, 425, 442, 459, 477, 495, 513, 532, 551, 570, 590

Offset: 0

N. J. A. Sloane

a(n-3) is the number of aperiodic necklaces (Lyndon words) with 3 black beads and n-3 white beads.
Number of triangular partitions (see Almkvist).
Consists of arithmetic progression quadruples of common difference n+1 starting at A045943(n). Refers to the least number of coins needed to be rearranged in order to invert the pattern of a (n+1)-rowed triangular array. For instance, a 5-rowed triangular array requires a minimum of a(4)=5 rearrangements (shown bracketed here) for it to be turned upside down.
  .....{*}..................{*}*.*{*}{*}
  .....*.*....................*.*.*.{*}
  ....*.*.*....---------\......*.*.*
  ..{*}*.*.*...---------/.......*.*
  {*}{*}*.*{*}..................{*}
  - Lekraj Beedassy, Oct 13 2003
Partial sums of 1,1,1,2,2,2,3,3,3,4,4,4,... - Jon Perry, Mar 01 2004
Sum of three successive terms is a triangular number in natural order starting with 3: a(n)+a(n+1)+a(n+2) = T(n+2) = (n+2)*(n+3)/2. - Amarnath Murthy, Apr 25 2004
Apply Riordan array (1/(1-x^3),x) to n. - Paul Barry, Apr 16 2005
Absolute values of numbers that appear in A145919. - Matthew Vandermast, Oct 28 2008
In the Moree definition, (-1)^n*a(n) is the 3rd Witt transform of A033999 and (-1)^n*A004524(n) with 2 leading zeros dropped is the 2nd Witt transform of A033999. - R. J. Mathar, Nov 08 2008
Column sums of:
1 2 3 4 5 6 7  8  9.....
      1 2 3 4  5  6.....
            1  2  3.....
........................
----------------------
1 2 3 5 7 9 12 15 18  - Jon Perry, Nov 16 2010
a(n) is the sum of the positive integers <= n that have the same residue modulo 3 as n. They are the additive counterpart of the triple factorial numbers. - Peter Luschny, Jul 06 2011
a(n+1) is the number of 3-tuples (w,x,y) with all terms in {0,...,n} and w=3*x+y. - Clark Kimberling, Jun 04 2012
a(n+1) is the number of pairs (x,y) with x and y in {0,...,n}, x-y = (1 mod 3), and x+y < n. - Clark Kimberling, Jul 02 2012
a(n+1) is the number of partitions of n into two sorts of part(s) 1 and one sort of (part) 3. - Joerg Arndt, Jun 10 2013
Arrange A004523 in rows successively shifted to the right two spaces and sum the columns:
1  2  2  3  4  4  5  6  6...
      1  2  2  3  4  4  5...
            1  2  2  3  4...
                  1  2  2...
                        1...
------------------------------
1  2  3  5  7  9 12 15 18... - L. Edson Jeffery, Jul 30 2014
a(n) = A258708(n+1,1) for n > 0. - Reinhard Zumkeller, Jun 23 2015
Also the number of triples of positive integers summing to n + 4, the first less than each of the other two. Also the number of triples of positive integers summing to n + 2, the first less than or equal to each of the other two. - Gus Wiseman, Oct 11 2020
Also the lower matching number of the (n+1)-triangular honeycomb king graph = n-triangular grid graph (West convention). - Eric W. Weisstein, Dec 14 2024

			G.f. = x + 2*x^2 + 3*x^3 + 5*x^4 + 7*x^5 + 9*x^6 + 12*x^7 + 15*x^8 + 18*x^9 + ...
1+2+3=6=t(3), 2+3+5=t(4), 5+7+9=t(5).
[n] a(n)
--------
[1] 1
[2] 2
[3] 3
[4] 1 + 4
[5] 2 + 5
[6] 3 + 6
[7] 1 + 4 + 7
[8] 2 + 5 + 8
[9] 3 + 6 + 9
a(7) = floor(2/3) +floor(3/3) +floor(4/3) +floor(5/3) +floor(6/3) +floor(7/3) +floor(8/3) +floor(9/3) = 12. - _Bruno Berselli_, Aug 29 2013

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 73, problem 25.
Ulrich Faigle, Review of Gerhard Post and G.J. Woeginger, Sports tournaments, home-away assignments and the break minimization problem, MR2224983(2007b:90134), 2007.
Hansraj Gupta, Partitions of j-partite numbers into twelve or a smaller number of parts. Collection of articles dedicated to Professor P. L. Bhatnagar on his sixtieth birthday. Math. Student 40 (1972), 401-441 (1974).
Richard 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, (p. 126, divided by 2).
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).

T. D. Noe, Table of n, a(n) for n = 0..1000
Chwas Ahmed, Paul Martin, and Volodymyr Mazorchuk, On the number of principal ideals in d-tonal partition monoids, arXiv preprint arXiv:1503.06718 [math.CO], 2015.
Gert Almkvist, Asymptotic formulas and generalized Dedekind sums, Exper. Math., 7 (No. 4, 1998), pp. 343-359.
David J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.
David Broadhurst and Xavier Roulleau, Number of partitions of modular integers, arXiv:2502.19523 [math.NT], 2025. See p. 19.
Cristian Cobeli, Aaditya Raghavan, and Alexandru Zaharescu, On the central ball in a translation invariant involutive field, arXiv:2408.01864 [math.NT], 2024. See p. 7.
Neville de Mestre and John Baker, Pebbles, Ducks and Other Surprises, Australian Maths. Teacher, Vol. 48, No 3, 1992, pp. 4-7.
Peter M. Chema, Illustration of first 27 terms as corners of a double hexagon spiral from 0
H. Gupta, Partitions of j-partite numbers into twelve or a smaller number of parts, Math. Student 40 (1972), 401-441 (1974). [Annotated scanned copy]
Richard K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 207.
Clark Kimberling, A Combinatorial Classification of Triangle Centers on the Line at Infinity, J. Int. Seq., Vol. 22 (2019), Article 19.5.4.
Clark Kimberling and John E. Brown, Partial Complements and Transposable Dispersions, J. Integer Seqs., Vol. 7, 2004.
R. P. Loh, A. G. Shannon, and A. F. Horadam, Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients, Preprint, 1980.
Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160.
Brian O'Sullivan and Thomas Busch, Spontaneous emission in ultra-cold spin-polarised anisotropic Fermi seas, arXiv 0810.0231v1 [quant-ph], 2008. [Eq 8a, lambda=3]
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Gerhard Post and G. J. Woeginger, Sports tournaments, home-away assignments and the break minimization problem, Discrete Optimization 3, pp. 165-173, 2006.
Michael Somos, Somos Polynomials.
Gary E. Stevens, A Connell-Like Sequence, J. Integer Seqs., 1 (1998), Article 98.1.4.
Andrei K. Svinin, On some class of sums, arXiv:1610.05387 [math.CO], 2016. See p. 7.
Eric Weisstein's World of Mathematics, Lower Matching Number.
Eric Weisstein's World of Mathematics, Triangular Grid Graph.
Eric Weisstein's World of Mathematics, Triangular Honeycomb King Graph.
Index entries for sequences related to Lyndon words.
Index entries for two-way infinite sequences.
Index entries for linear recurrences with constant coefficients, signature (2,-1,1,-2,1).

Cf. A000031, A001037, A008748, A051168.
Ordered union of triangular matchstick numbers A045943 and generalized pentagonal numbers A001318.
Cf. A058937.
A column of triangle A011847.
Cf. A000217, A130205.
Cf. A258708.
A001399 counts 3-part partitions, ranked by A014612.
A337483 counts either weakly increasing or weakly decreasing triples.
A337484 counts neither strictly increasing nor strictly decreasing triples.
A014311 ranks 3-part compositions, with strict case A337453.
Cf. A007052, A007304, A011782, A069905, A156040, A218004.

a001840 n = a001840_list !! n
a001840_list = scanl (+) 0 a008620_list
-- Reinhard Zumkeller, Apr 16 2012

[ n le 2 select n else n*(n+1)/2-Self(n-1)-Self(n-2): n in [1..58] ];  // Klaus Brockhaus, Oct 01 2009

A001840 := n->floor((n+1)*(n+2)/6);
A001840:=-1/((z**2+z+1)*(z-1)**3); # conjectured (correctly) by Simon Plouffe in his 1992 dissertation
seq(floor(binomial(n-1,2)/3), n=3..61); # Zerinvary Lajos, Jan 12 2009
A001840 :=  n -> add(k, k = select(k -> k mod 3 = n mod 3, [$1 .. n])): seq(A001840(n), n = 0 .. 58); # Peter Luschny, Jul 06 2011

a[0]=0; a[1]=1; a[n_]:= a[n]= n(n+1)/2 -a[n-1] -a[n-2]; Table[a[n], {n,0,100}]
f[n_] := Floor[(n + 1)(n + 2)/6]; Array[f, 59, 0] (* Or *)
CoefficientList[ Series[ x/((1 + x + x^2)*(1 - x)^3), {x, 0, 58}], x] (* Robert G. Wilson v *)
a[ n_] := With[{m = If[ n < 0, -3 - n, n]}, SeriesCoefficient[ x /((1 - x^3) (1 - x)^2), {x, 0, m}]]; (* Michael Somos, Jul 11 2011 *)
LinearRecurrence[{2,-1,1,-2,1},{0,1,2,3,5},60] (* Harvey P. Dale, Jul 25 2011 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n+4,{3}],#[[1]]<#[[2]]&&#[[1]]<#[[3]]&]],{n,0,15}] (* Gus Wiseman, Oct 05 2020 *)

{a(n) = (n+1) * (n+2) \ 6}; /* Michael Somos, Feb 11 2004 */

[binomial(n, 2) // 3 for n in range(2, 61)] # Zerinvary Lajos, Dec 01 2009

a(n) = (A000217(n+1) - A022003(n-1))/3;
a(n) = (A016754(n+1) - A010881(A016754(n+1)))/24;
a(n) = (A033996(n+1) - A010881(A033996(n+1)))/24.
Euler transform of length 3 sequence [2, 0, 1].
a(3*k-1) = k*(3*k + 1)/2;
a(3*k)   = 3*k*(k + 1)/2;
a(3*k+1) = (k + 1)*(3*k + 2)/2.
a(n) = floor( (n+1)*(n+2)/6 ) = floor( A000217(n+1)/3 ).
a(n+1) = a(n) + A008620(n) = A002264(n+3). - Reinhard Zumkeller, Aug 01 2002
From Michael Somos, Feb 11 2004: (Start)
G.f.: x / ((1-x)^2 * (1-x^3)).
a(n) = 1 + a(n-1) + a(n-3) - a(n-4).
a(-3-n) = a(n). (End)
a(n) = a(n-3) + n for n > 2; a(0)=0, a(1)=1, a(2)=2. - Paul Barry, Jul 14 2004
a(n) = binomial(n+3, 3)/(n+3) + cos(2*Pi*(n-1)/3)/9 + sqrt(3)sin(2*Pi*(n-1)/3)/9 - 1/9. - Paul Barry, Jan 01 2005
From Paul Barry, Apr 16 2005: (Start)
a(n) = Sum_{k=0..n} k*(cos(2*Pi*(n-k)/3 + Pi/3)/3 + sqrt(3)*sin(2*Pi*(n-k)/3 + Pi/3)/3 + 1/3).
a(n) = Sum_{k=0..floor(n/3)} n-3*k. (End)
For n > 1, a(n) = A000217(n) - a(n-1) - a(n-2); a(0)=0, a(1)=1.
G.f.: x/(1 + x + x^2)/(1 - x)^3. - Maksym Voznyy (voznyy(AT)mail.ru), Jul 27 2009
a(n) = (4 + 3*n^2 + 9*n)/18 + ((n mod 3) - ((n-1) mod 3))/9. - Klaus Brockhaus, Oct 01 2009
a(n) = 2*a(n-1) - a(n-2) + a(n-3) - 2*a(n-4) + a(n-5), with n>4, a(0)=0, a(1)=1, a(2)=2, a(3)=3, a(4)=5. - Harvey P. Dale, Jul 25 2011
a(n) = A214734(n + 2, 1, 3). - Renzo Benedetti, Aug 27 2012
G.f.: x*G(0), where G(k) = 1 + x*(3*k+4)/(3*k + 2 - 3*x*(k+2)*(3*k+2)/(3*(1+x)*k + 6*x + 4 - x*(3*k+4)*(3*k+5)/(x*(3*k+5) + 3*(k+1)/G(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Jun 10 2013
Empirical: a(n) = floor((n+3)/(e^(6/(n+3))-1)). - Richard R. Forberg, Jul 24 2013
a(n) = Sum_{i=0..n} floor((i+2)/3). - Bruno Berselli, Aug 29 2013
0 = a(n)*(a(n+2) + a(n+3)) + a(n+1)*(-2*a(n+2) - a(n+3) + a(n+4)) + a(n+2)*(a(n+2) - 2*a(n+3) + a(n+4)) for all n in Z. - Michael Somos, Jan 22 2014
a(n) = n/2 + floor(n^2/3 + 2/3)/2. - Bruno Berselli, Jan 23 2017
a(n) + a(n+1) = A000212(n+2). - R. J. Mathar, Jan 14 2021
Sum_{n>=1} 1/a(n) = 20/3 - 2*Pi/sqrt(3). - Amiram Eldar, Sep 27 2022
E.g.f.: (exp(x)*(4 + 12*x + 3*x^2) - 4*exp(-x/2)*cos(sqrt(3)*x/2))/18. - Stefano Spezia, Apr 05 2023

A001198 Zarankiewicz's problem k_3(n).

Original entry on oeis.org

9, 14, 21, 27, 34, 43, 50, 61, 70, 81, 93, 106, 121, 129

Offset: 3

N. J. A. Sloane

Guy denotes k_{a,b}(m,n) the least k such that any m X n matrix with k '1's and '0's elsewhere has an a X b submatrix with all '1's, and omits b (resp. n) when b = a (resp. n = m). With this notation, a(n) = k_3(n). Sierpiński (1951) found a(4..6), a(7) is due to Brzeziński and a(8) due to Čulík (1956). - M. F. Hasler, Sep 28 2021

			From _M. F. Hasler_, Sep 28 2021: (Start)
For n = 3 it is clearly necessary and sufficient that there be 3 X 3 = 9 ones in the n X n matrix in order to have an all-ones 3 X 3 submatrix.
For n = 4 there may be at most 2 zeros in the 4 X 4 matrix in order to be guaranteed to have a 3 X 3 submatrix with all '1's, whence a(4) = 16 - 2 = 14: If 3 zeros are placed on a diagonal, it is no more possible to find a 3 X 3 all-ones submatrix, but if there are at most 2 zeros, one always has such a submatrix, as one can see from the following two diagrams:
                                       0 1 1 1        0 1 1 1      no 3 X 3
     Here one can delete, e.g.,   ->   1 0 1 1        1 0 1 1  <-  all-ones
     row 1 and column 2 to get         1 1 1 1        1 1 0 1      submatrix
     an all-ones 3 X 3 matrix.         1 1 1 1        1 1 1 1        (End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 291.
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).

R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.
Jeremy Tan, An attack on Zarankiewicz's problem through SAT solving, arXiv:2203.02283 [math.CO], 2022.

Cf. A001197 (k_2(n)), A006613 (k_{2,3}(n)), ..., A006626 (k_4(n,n+1)).

Cf. A339635, A347473, A350237, A350304.

a(n) = A350304(n) + 1 = n^2 - A347473(n) = n^2 - A350237(n) + 1. - Andrew Howroyd, Dec 26 2021

a(11)-a(13) from Andrew Howroyd, Dec 26 2021
a(14)-a(15) computed from A350237 by Max Alekseyev, Apr 01 2022
a(16) from Jeremy Tan, Oct 02 2022

A072567 A variant of Zarankiewicz problem: maximal number of 1s in n X n 01-matrix with no four 1s forming a rectangle.

Original entry on oeis.org

1, 3, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45, 52, 56, 61, 67, 74, 81, 88, 96, 105, 108, 115, 122

Offset: 1

Xuli Le (leshlie(AT)eyou.com), Jun 21 2002

Proving a(13) < 53 and finding a(7) were problems at the 1975 USSR National Olympiad and are presented in the Ross Honsberger 1985 book "Mathematical Gems III" (see links). - Tanya Khovanova, Oct 12 2007
The growth rate of a(n) is O(n^{3/2}). For a lower bound, take the incidence graph of a finite projective plane. For prime powers q, you get a(q^2+q+1) >= (q+1)(q^2+q+1). For an upper bound, the matrix is an adjacency matrix of a bipartite graph of girth 6. These have at most O(n^{3/2}) edges. - Peter Shor, Jul 01 2013
Conjecture: the same number of 1s is achieved for symmetric n X n matrices (cf. A350189). - Max Alekseyev, Apr 03 2022

			Examples of a(2)=3, a(3)=6, and a(4)=9:
11   110   1110
10   101   1001
     011   0101
           0011
a(4)=9 is also achieved at a symmetric matrix:
0111
1010
1100
1001 - _Max Alekseyev_, Apr 03 2022

Brendan McKay's Largest graphs of girth at least 6, MathOverflow, 2012. [The number of edges given there for even n seem to be the terms of this sequence. They are certainly bounded above by them.]
Stefan Neuwirth, The size of bipartite graphs with girth eight, arXiv:math/0102210 [math.CO], 2001.
I. Reiman, Über ein Problem von K. Zarankiewicz, Acta Mathematica Academiae Scientiarum Hungarica, Volume 9, Issue 3-4 , pp 269-273.
R. Honsberger, Two Problems from the 1974 USSR National Olympiad (#4 and #9). Excerpt from "Mathematical Gems III" book, 1985. [In fact, these problems are from the olympiad of 1975, not 1974, and were published as Problem M335 in Kvant 7 (1975).]
E. Belaga, Solution to Problem M335, Kvant 3 (1976), 42-44. (in Russian)

Cf. A001197.

For prime powers q, a(q^2+q+1) = (q+1)(q^2+q+1). It follows from equality case of Reiman inequality. For example, a(21)=105 and a(31)=186. - Senya Karpenko, Jul 23 2014

a(n) = A001197(n) - 1 for n>=2. - Rob Pratt, Aug 09 2019

a(1) = 1 from Don Reble, Oct 13 2007
More terms (using formula and A001197) from Rob Pratt, Aug 09 2019
a(22)-a(24) from Jeremy Tan, Jan 23 2022
Edited by Max Alekseyev, Apr 03 2022

A006613 Zarankiewicz's problem.

Original entry on oeis.org

8, 13, 17, 22, 29, 34, 40, 47, 56

Offset: 3

N. J. A. Sloane

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

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

R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.

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

Original entry on oeis.org

0, 2, 4, 9, 15, 21, 31, 39, 51, 63, 76, 90, 104, 127

Offset: 3

M. F. Hasler, Sep 28 2021

Related to Zarankiewicz's problem k_3(n) (cf. A001198 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 3 X 3 submatrix. This complementarity leads to the given formula which was used to compute the given values.

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

Cf. A001198 (k_3(n)), A001197 (k_2(n)), A006613 - A006626 (other sizes of the main matrix and the submatrix).
Cf. A347472, A347474 (analog for 2 X 2 resp. 4 X 4 zero submatrix).
Cf. A339635, A350237, A350304.

a(n) = n^2 - A001198(n).
a(n) = A350237(n) - 1. - Andrew Howroyd, Dec 24 2021
a(n) = n^2 - A350304(n) - 1. - Max Alekseyev, Oct 31 2022

a(11)-a(13) from Andrew Howroyd, Dec 24 2021

a(14)-a(16) computed from A350237 by Max Alekseyev, Apr 01 2022, Oct 31 2022

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

Original entry on oeis.org

0, 2, 4, 6, 12, 19, 25, 34, 43, 51

Offset: 4

M. F. Hasler, Sep 28 2021

Related to Zarankiewicz's problem k_4(n) (cf. A006616 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 4 X 4 submatrix. This complementarity leads to the given formula which was used to compute the given values.

			For n < 4, there is no solution, since there cannot be a 4 X 4 submatrix in a matrix of smaller size.
For n = 4, there must not be any nonzero entry in an n X n = 4 X 4 matrix, if one wants a 4 X 4 zero submatrix, whence a(4) = 0.
For n = 5, having at most 2 nonzero entries in the n X n matrix guarantees that there is a 4 X 4 zero submatrix (delete, e.g., the row with the first nonzero entry, then the column with the second nonzero entry, if any), but if one allows 3 nonzero entries and they are placed on the diagonal, then there is no 4 X 4 zero submatrix. Hence, a(5) = 2.

Cf. A347472, A347473 (analog for 2 X 2 resp. 3 X 3 zero submatrix).
Cf. A006616 (k_4(n)), A001198 (k_3(n)), A001197 (k_2(n)), A006613 - A006626.
Cf. A339635.

a(n) = n^2 - A006616(n).

a(n) = A339635(n,4) - 1. - Andrew Howroyd, Dec 23 2021

a(9)-a(12) from Andrew Howroyd, Dec 23 2021

a(13) computed from A006616 by Max Alekseyev, Feb 02 2024

A006616 Zarankiewicz's problem k_4(n).

Original entry on oeis.org

16, 23, 32, 43, 52, 62, 75, 87, 101, 118

Offset: 4

N. J. A. Sloane

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

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

R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.
Dmitry I. Ignatov, When contranominal scales give a solution to the Zarankiewicz problem?, Workshop Notes, 12th Int'l Wksp. Formal Concept Analysis Artif. Intel. (FCA4AI 2024), 27-38. See p. 34.

Cf. A001197, A001198, A006626, A339635, A347474.

a(n) = n^2 - A347474(n). - Andrew Howroyd, Dec 26 2021

a(9)-a(13) from Andrew Howroyd, Dec 26 2021

A191873 A problem of Zarankiewicz: maximal number of 1's in an n X n matrix of 0's and 1's with 0's on the main diagonal and no "rectangle" with 1's at the four corners.

Original entry on oeis.org

0, 2, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45

Offset: 1

R. H. Hardin and N. J. A. Sloane, Jun 18 2011

In other words, the pattern
  1...1
  .....
  1...1
is forbidden.
From Don Knuth, Aug 13 2014: (Start)
Well, it is well known from A001197 that a(8)<25. A001197 is essentially the same problem, but increased by 1, and without restricting the diagonals. The diagonal restriction is however of little interest, because it's easy to permute rows and columns and get all 0's or all 1's or probably any of the 2^n possible settings of the diagonal. At least, this is true when n=8; hence a(8) in this sequence is 24.
Transposing cols 1<->4 and 5<->8 in the example by Guy 1967 page 130 as cited in A001197 gives a(8)=24:
  01110000
  10010100
  00010011
  01000101
  10100010
  11001000
  00101001
  00001110
But as stated above, I think this is quite trivial, and I believe this sequence should be downplayed. Readers should look at the sequence A001197 --- that's what Zarankiewicz's problem asked for in 1951, namely the min number that forces a rectangle, not the max number that doesn't exclude it. (End)
Conjecture: for n >= 3, a(n) = A072567(n) = A001197(n) - 1 (per above comment). - Max Alekseyev, Jan 29 2022

B. Bollobas, Extremal Graph Theory, pp. 309ff.

D. Bienstock and E. Gyori, An extremal problem on sparse 0-1 matrices, SIAM J. Discrete Math. 4 (1991), 17-27.

Cf. A072567, A191874, A191965, A191966.

a(8) confirmed, a(9)-a(12) added by Max Alekseyev, Feb 07 2022

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

Original entry on oeis.org

0, 0, 1, 1, 2, 4, 7, 8, 12, 13, 17, 20, 26, 28, 35, 37, 44, 48, 57, 60, 70, 73, 83, 88, 100, 104, 117, 121, 134, 140, 155, 160, 176, 181, 197, 204, 222, 228, 247, 253, 272, 280, 301, 308, 330, 337, 359, 368, 392, 400, 425, 433, 458, 468, 495, 504, 532, 541, 569, 580, 610, 620, 651, 661, 692, 704, 737, 748, 782, 793

Offset: 1

N. J. A. Sloane

Maximum number of edge-disjoint K_3's in a K_n.
Maximum number of clauses in a reduced 1 in 3 SAT instance. Given N items taken three at a time, what is the maximum number of combinations such that no two combinations share more than one item in common. There are reduction rules for 1 in 3 SAT that guarantee no two clauses share more than one variable in common. a(n) is the maximum number of clauses a reduced instance with n variables can have. Example: a(6)=4: (a,b,c)(a,d,e)(b,d,f)(c,e,f). - Russell Easterly, Oct 02 2005
Agrees with independence number of the n-tetrahedral graph for at least a(6)-a(12). - Eric W. Weisstein, Jun 14 2017 and Jul 24 2017
Packing number D(n,3,2). - Rob Pratt, Feb 26 2024

			Codes illustrating A(4,3,4) = a(3) = 1, A(5,3,4) = a(5) = 2 and A(6,3,4) = a(6) = 4 are:
   1110...11100..111000
   .......10011..100110
   ..............010101
   ..............001011

P. J. Cameron, Combinatorics, ..., Cambridge, 1994, see p. 121.
CRC Handbook of Combinatorial Designs, 1996, p. 411.
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).

T. D. Noe, Table of n, a(n) for n = 1..10000
A. E. Brouwer, Bounds for constant weight binary codes
A. E. Brouwer, J. B. Shearer, N. J. A. Sloane and W. D. Smith, New table of constant weight codes, IEEE Trans. Info. Theory 36 (1990), 1334-1380.
P. Erdős et al., Edge disjoint monochromatic triangles in 2-colored graphs, Discrete Math., 231 (2001), 135-141.
R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
Alice Miller and Michael Codish, Graphs with girth at least 5 with orders between 20 and 32, arXiv:1708.06576 [math.CO], 2017, Table 3.
Eric Weisstein's World of Mathematics, Independence Number
Eric Weisstein's World of Mathematics, Tetrahedral Graph
Index entries for sequences related to A(n,d,w)
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,0,0,1,-1,-1,1).

Cf. A001843, A011975, A060407.

Table[Floor[n Floor[(n - 1)/2]/3] - Boole[Mod[n, 6] == 5], {n, 20}] (* Eric W. Weisstein, Jul 13 2017 *)
Table[(6 n^2 - 9 n - 10 - 3 (-1)^n (n - 2) - 6 Cos[n Pi/3] + 10 Cos[2 n Pi/3] + 10 Sqrt[3] Sin[n Pi/3] + 6 Sqrt[3] Sin[2 n Pi/3])/36, {n, 20}]  (* Eric W. Weisstein, Jul 13 2017 *)
LinearRecurrence[{1, 1, -1, 0, 0, 1, -1, -1, 1}, {0, 0, 1, 1, 2, 4, 7,
   8, 12}, 20] (* Eric W. Weisstein, Jul 13 2017 *)
CoefficientList[Series[(x^2 (-1 - 2 x^3 - 2 x^4 + x^5))/((-1 + x)^3 (1 + x)^2 (1 - x + x^2) (1 + x + x^2)), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 13 2017 *)

Known exactly for all n - see Theorem 4 of Brouwer et al. (1990): A(n, 4, 3) = floor((n/3)*floor((n-1)/2))-1 if n is congruent to 5 (mod 6) and A(n, 4, 3) = floor((n/3)*floor((n-1)/2)) if n is not congruent to 5 (mod 6). - Shelly Jones (shellysalt(AT)yahoo.com), Apr 27 2004
a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9). - Eric W. Weisstein, Jul 13 2017
G.f.: x^3*(x^5-2*x^4-2*x^3-1) / ((x-1)^3*(x+1)^2*(x^2-x+1)*(x^2+x+1)). - Colin Barker, Sep 21 2013

More terms from Shelly Jones (shellysalt(AT)yahoo.com), Apr 27 2004

cp's OEIS Frontend

A001840 Expansion of g.f. x/((1 - x)^2*(1 - x^3)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

A001198 Zarankiewicz's problem k_3(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A072567 A variant of Zarankiewicz problem: maximal number of 1s in n X n 01-matrix with no four 1s forming a rectangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A006613 Zarankiewicz's problem.

Views

Author

Keywords

Comments

References

Links

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A006616 Zarankiewicz's problem k_4(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A191873 A problem of Zarankiewicz: maximal number of 1's in an n X n matrix of 0's and 1's with 0's on the main diagonal and no "rectangle" with 1's at the four corners.

Views

Author

Keywords

Comments

References