|
%I #59 Mar 08 2022 15:51:57
%S 0,0,0,0,1,1,2,3,4,6,7,9,11,13,15,18,20,23,26,29,33,36,40,44,48,52,57,
%T 61,66,71,76,82,87,93,99,105,111,118,124,131,138,145,153,160,168,176,
%U 184,192,201,209,218,227,236,246,255,265,275,285,295,306,316,327,338
%N Minimum number of monochromatic Schur triples over all 2-colorings of [n].
%C A Schur triple is an integer triple (x,y,x+y). A 2-coloring on [n] = {1,...,n} is a surjective map [n] --> {Red, Blue}. A triple (x,y,z) is monochromatic if the set {x,y,z} is mapped to one color. a(n) is exactly the minimum number of monochromatic Schur triples over all possible 2-colorings of [n]. The "optimal" coloring for all n (i.e. the coloring that produces the minimum number of monochromatic Schur triples) was shown by Robertson and Zeilberger in 1998 and later with a greedy algorithm by Thanatipanonda in 2009 (see the example for the optimal coloring of [11]). The exact formula for a(n) is computed based on this optimal coloring. One might notice in the literature that there is an additional assumption x<=y. We do not impose this constraint.
%H Elaine Wong, <a href="/A321195/b321195.txt">Table of n, a(n) for n = 1..1000</a>
%H B. Datskovsky, <a href="https://doi.org/10.1016/S0196-8858(03)00010-1">On the number of monochromatic Schur triples</a>, Advances in Applied Math, 31 (2003), 193-198.
%H C. Koutschan and E. Wong, <a href="https://doi.org/10.1007/978-3-030-44559-1_13">Exact Lower Bounds for Monochromatic Schur Triples and Generalizations</a>, In: Pillwein V., Schneider C. (eds) Algorithmic Combinatorics: Enumerative Combinatorics, Special Functions and Computer Algebra. Texts & Monographs in Symbolic Computation (A Series of the Research Institute for Symbolic Computation, Johannes Kepler University, Linz, Austria), Springer, pp.223-248 (2020).
%H A. Robertson and D. Zeilberger, <a href="https://doi.org/10.37236/1357">A 2-coloring of [1,n] can have n^2/22+O(n) monochromatic Schur triples, but not less!</a>, The Electronic Journal of Combinatorics, 5 #R19 (1998).
%H T. Schoen, <a href="https://doi.org/10.1006/eujc.1999.0297">The number of monochromatic Schur Triples</a>, European Journal of Combinatorics, 20 (1999), 855-866.
%H T. Thanatipanonda, <a href="https://doi.org/10.37236/103">On the Monochromatic Schur Triples Type Problem</a>, The Electronic Journal of Combinatorics, 16(1) #R14 (2009).
%H T. Thanatipanonda and E. Wong, <a href="https://doi.org/10.37236/6490">On the Minimum Number of Monochromatic Generalized Schur Triples</a>, The Electronic Journal of Combinatorics, 24(2), P.2.20 (2017).
%H <a href="/index/Rec#order_13">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,0,0,0,0,0,0,0,0,1,-2,1).
%F a(n) = floor((n^2 - 4*n + 6)/11).
%F G.f.: (-x^5 + x^6 - x^7 - x^10 + x^11 - x^12)/ (-1 + 2*x - x^2 + x^11 - 2*x^12 + x^13).
%F a(n) = 2*a(n-1) - a(n-2) + a(n-11) - 2*a(n-12) + a(n-13) for n > 13. - _Colin Barker_, Dec 18 2018
%e On the interval [11], the optimal coloring is R,R,R,R,B,B,B,B,B,B,R, which produces a minimum 7 monochromatic triples (x,y,x+y): (1,1,2), (1,2,3), (2,1,3), (1,3,4), (2,2,4), (3,1,4), (5,5,10).
%p seq(floor((n^2-4*n+6)/11), n=1..1000);
%t Table[Floor[(n^2-4n+6)/11], {n,1000}]
%o (GAP) List([1..100],n->Int((n^2-4*n+6)/11)); # _Muniru A Asiru_, Dec 19 2018
%K nonn
%O 1,7
%A _Elaine Wong_, Dec 18 2018
|
