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

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,5

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

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

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

Example

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

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

Crossrefs

Cf. A001843, A011975, A060407.

Sequence in context: A187346 A184414 A060406 * A087686 A232054 A216431

Adjacent sequences: A001836 A001837 A001838 * A001840 A001841 A001842

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

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

Status

approved