|
| |
|
|
A001839
|
|
The coding-theoretic function A(n,4,3).
(Formerly M1032 N0389)
|
|
6
|
|
|
|
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;
text;
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. 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
|
|
|
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
|
| |
|
|
