|
| |
|
|
A001839
|
|
The coding-theoretic function A(n,4,3).
(Formerly M1032 N0389)
|
|
4
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,5
|
|
|
COMMENTS
| Maximal 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. This series 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 (logiclab(AT)comcast.net), Oct 02 2005
|
|
|
REFERENCES
| 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. J. Cameron, Combinatorics, ..., Cambridge, 1994, see p. 121.
CRC Handbook of Combinatorial Designs, 1996, p. 411.
P. Erdos et al., Edge disjoint monochromatic triangles in 2-colored graphs, Discrete Math., 231 (2001), 135-141.
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
Index entries for sequences related to A(n,d,w)
|
|
|
FORMULA
| Known exactly for all n - see Theorem 4 of Brouwer et al.: 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)
|
|
|
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:
11110..11100..111000
.......10011..100110
..............010101
..............001011
|
|
|
MATHEMATICA
| Table[tmp = Floor[(n/3)*Floor[(n - 1)/2]]; If[Mod[n, 6] == 5, tmp - 1, tmp], {n, 100}] (* T. D. Noe, Sep 19 2011 *)
|
|
|
CROSSREFS
| Cf. A060407, A001843, A011975.
Sequence in context: A187346 A184414 A060406 * A087686 A088413 A090669
Adjacent sequences: A001836 A001837 A001838 * A001840 A001841 A001842
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms and formula from Shelly Jones (shellysalt(AT)yahoo.com), Apr 27 2004
|
| |
|
|
