A001843 -id:A001843 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 8, 16, 20, 40, 72, 144, 256, 512, 1024, 2048

Offset: 1

N. J. A. Sloane

Since A(n,3) = A(n+1,4), A(n,3) gives essentially the same sequence.
The next term a(17) is in the range 2816-3276.
Let T_n be the set of SDS-maps of sequential dynamical systems defined over the complete graph K_n in which all vertices have the same vertex function (defined using a set of two possible vertex states). Then a(n) is the maximum number of period-2 orbits that a function in T_n can have. - Colin Defant, Sep 15 2015
Since the n-halved cube graph is isomorphic to (or, if you prefer, defined as) the graph with binary sequences of length n-1 as nodes and edges between pairs of sequences that differ in at most two positions, the independence number of the n-halved cube graph is A(n-1,3) = a(n). - Pontus von Brömssen, Dec 12 2018
a(2^k) = A(2^k-1, 3) = 2^(2^k-k-1) because the hypercube Q(2^k-1) can be perfectly packed with radius-1 spheres, corresponding to a Hamming(2^k-1, 2^k-k-1) code. - Yifan Xie, May 06 2025

J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer-Verlag, p. 248.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 674.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

A. E. Brouwer, Tables of general 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.
Colin Defant, Binary Codes and Period-2 Orbits of Sequential Dynamical Systems, arXiv:1509.03907 [math.CO], 2015.
Moshe Milshtein, A new binary code of length 16 and minimum distance 3, Information Processing Letters 115.12 (2015): 975-976.
Patric R. J. Östergård (patric.ostergard(AT)hut.fi), T. Baicheva and E. Kolev, Optimal binary one-error-correcting codes of length 10 have 72 codewords, IEEE Trans. Inform. Theory, 45 (1999), 1229-1231.
A. M. Romanov, New binary codes with minimal distance 3, Problemy Peredachi Informatsii, 19 (1983) 101-102.
Eric Weisstein's World of Mathematics, Error-Correcting Code
Eric Weisstein's World of Mathematics, Halved Cube Graph
Eric Weisstein's World of Mathematics, Independence Number
Wikipedia, Halved cube graph
Index entries for sequences related to A(n,d)

Cf. A005865: A(n,6) ~ A(n,5), A005866: A(n,8) ~ A(n,7).

Cf. A001839: A(n,4,3), A001843: A(n,4,4), A169763: A(n,4,5).

A351100 Maximum number of 4-subsets of an n-set such that every 3-subset is covered at most twice.

Original entry on oeis.org

2, 5, 9, 15, 28, 40, 60, 80, 108, 143, 182, 225, 280, 340, 405

Offset: 4

Jeremy Tan, Jan 31 2022

Maximum number of K_4^3's that can be packed in a doubled K_n^3, where K_n^m is the complete m-uniform hypergraph on n vertices.

			a(6) = 9 because of the following optimal collection of 4-subsets:
  1 2 3 4
  2 3 4 5
  3 4 5 6
  4 5 6 1
  5 6 1 2
  6 1 2 3
  1 2 4 5
  2 3 5 6
  3 4 6 1

Richard K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Department of Mathematics, University of Calgary, January 1967. [Annotated and scanned copy, with permission]
Haim Hanani, On quadruple systems, Canadian Journal of Mathematics, 12 (1960), 145-157.
Jeremy Tan, An attack on Zarankiewicz's problem through SAT solving, arXiv:2203.02283 [math.CO], 2022.

Cf. A001839-A001843 for other packing sequences discussed in Richard K. Guy's paper.

a(n) >= 2*A001843(n). Equality holds if n = 6k+2 or 6k+4 (Hanani).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

A351100 Maximum number of 4-subsets of an n-set such that every 3-subset is covered at most twice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula