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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

Examples

			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
		

References

• 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).

Links

• 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).

Crossrefs

Cf. A001843, A011975, A060407.

Programs

Mathematica

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 *)

Formula

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

Extensions

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