|
%I M1032 N0389 #74 Feb 26 2024 19:40:39
%S 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,
%T 104,117,121,134,140,155,160,176,181,197,204,222,228,247,253,272,280,
%U 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
%N The coding-theoretic function A(n,4,3).
%C Maximum number of edge-disjoint K_3's in a K_n.
%C 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
%C 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
%C Packing number D(n,3,2). - _Rob Pratt_, Feb 26 2024
%D P. J. Cameron, Combinatorics, ..., Cambridge, 1994, see p. 121.
%D CRC Handbook of Combinatorial Designs, 1996, p. 411.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A001839/b001839.txt">Table of n, a(n) for n = 1..10000</a>
%H A. E. Brouwer, <a href="http://www.win.tue.nl/~aeb/codes/Andw.html">Bounds for constant weight binary codes</a>
%H A. E. Brouwer, J. B. Shearer, N. J. A. Sloane and W. D. Smith, <a href="http://dx.doi.org/10.1109/18.59932">New table of constant weight codes</a>, IEEE Trans. Info. Theory 36 (1990), 1334-1380.
%H P. Erdős et al., <a href="http://dx.doi.org/10.1016/S0012-365X(00)00312-5">Edge disjoint monochromatic triangles in 2-colored graphs</a>, Discrete Math., 231 (2001), 135-141.
%H R. K. Guy, <a href="/A001197/a001197.pdf">A problem of Zarankiewicz</a>, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
%H Alice Miller and Michael Codish, <a href="https://arxiv.org/abs/1708.06576">Graphs with girth at least 5 with orders between 20 and 32</a>, arXiv:1708.06576 [math.CO], 2017, Table 3.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependenceNumber.html">Independence Number</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TetrahedralGraph.html">Tetrahedral Graph</a>
%H <a href="/index/Aa#Andw">Index entries for sequences related to A(n,d,w)</a>
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1,0,0,1,-1,-1,1).
%F 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
%F 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
%F 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
%e 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:
%e 1110...11100..111000
%e .......10011..100110
%e ..............010101
%e ..............001011
%t Table[Floor[n Floor[(n - 1)/2]/3] - Boole[Mod[n, 6] == 5], {n, 20}] (* _Eric W. Weisstein_, Jul 13 2017 *)
%t 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 *)
%t LinearRecurrence[{1, 1, -1, 0, 0, 1, -1, -1, 1}, {0, 0, 1, 1, 2, 4, 7,
%t 8, 12}, 20] (* _Eric W. Weisstein_, Jul 13 2017 *)
%t 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 *)
%Y Cf. A001843, A011975, A060407.
%K nonn,easy,nice
%O 1,5
%A _N. J. A. Sloane_
%E More terms from Shelly Jones (shellysalt(AT)yahoo.com), Apr 27 2004
|
