OFFSET
1,7
COMMENTS
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.
LINKS
Elaine Wong, Table of n, a(n) for n = 1..1000
B. Datskovsky, On the number of monochromatic Schur triples, Advances in Applied Math, 31 (2003), 193-198.
C. Koutschan and E. Wong, Exact Lower Bounds for Monochromatic Schur Triples and Generalizations, 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).
A. Robertson and D. Zeilberger, A 2-coloring of [1,n] can have n^2/22+O(n) monochromatic Schur triples, but not less!, The Electronic Journal of Combinatorics, 5 #R19 (1998).
T. Schoen, The number of monochromatic Schur Triples, European Journal of Combinatorics, 20 (1999), 855-866.
T. Thanatipanonda, On the Monochromatic Schur Triples Type Problem, The Electronic Journal of Combinatorics, 16(1) #R14 (2009).
T. Thanatipanonda and E. Wong, On the Minimum Number of Monochromatic Generalized Schur Triples, The Electronic Journal of Combinatorics, 24(2), P.2.20 (2017).
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,0,0,0,0,0,0,1,-2,1).
FORMULA
a(n) = floor((n^2 - 4*n + 6)/11).
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).
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
EXAMPLE
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).
MAPLE
seq(floor((n^2-4*n+6)/11), n=1..1000);
MATHEMATICA
Table[Floor[(n^2-4n+6)/11], {n, 1000}]
PROG
(GAP) List([1..100], n->Int((n^2-4*n+6)/11)); # Muniru A Asiru, Dec 19 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Elaine Wong, Dec 18 2018
STATUS
approved