|
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
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
More terms and formula from Shelly Jones (shellysalt(AT)yahoo.com), Apr 27 2004
|
|
|
Search completed in 0.002 seconds
|
