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
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, 61, 66, 71, 76, 82, 87, 93, 99, 105, 111, 118, 124, 131, 138, 145, 153, 160, 168, 176, 184, 192, 201, 209, 218, 227, 236, 246, 255, 265, 275, 285, 295, 306, 316, 327, 338 (list; graph; refs; listen; history; text; internal format)
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.

A. Robertson and D. Zeilberger, A 2-coloring of [1,n] can have n^2/22+O(n) monochromatic Schur triples, but not less!, 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, Electronic Journal of Combinatorics, 16(1) #R14 (2009).

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

Sequence in context: A011865 A085680 A253186 * A249020 A258470 A248357

Adjacent sequences:  A321192 A321193 A321194 * A321196 A321197 A321198

KEYWORD

nonn

AUTHOR

Elaine Wong, Dec 18 2018

STATUS

approved

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 March 25 12:50 EDT 2019. Contains 321470 sequences. (Running on oeis4.)