login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A321195 Minimum number of monochromatic Schur triples over all 2-colorings of [n]. 1

%I

%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 A. Robertson and D. Zeilberger, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r19">A 2-coloring of [1,n] can have n^2/22+O(n) monochromatic Schur triples, but not less!</a>, 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="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r14">On the Monochromatic Schur Triples Type Problem</a>, Electronic Journal of Combinatorics, 16(1) #R14 (2009).

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 20 04:42 EDT 2019. Contains 322294 sequences. (Running on oeis4.)