|
Search: id:A001839
|
|
|
| A001839 |
|
The coding-theoretic function A(n,4,3).
(Formerly M1032 N0389)
|
|
+0
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
(list; graph; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
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.
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.
|
|
LINKS
|
E. M. Rains and N. J. A. Sloane, A(n,d,w) tables
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
|
|
CROSSREFS
|
Cf. A060407, A001843.
Sequence in context: A091996 A085262 A060406 this_sequence A087686 A088413 A090669
Adjacent sequences: A001836 A001837 A001838 this_sequence A001840 A001841 A001842
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
More terms and formula from Shelly Jones (shellysalt(AT)yahoo.com), Apr 27 2004
|
|
|
Search completed in 0.002 seconds
|
