

A321195


Minimum number of monochromatic Schur triples over all 2colorings 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 2coloring 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 2colorings 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), 193198.
A. Robertson and D. Zeilberger, A 2coloring 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), 855866.
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(n1)  a(n2) + a(n11)  2*a(n12) + a(n13) 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^24*n+6)/11), n=1..1000);


MATHEMATICA

Table[Floor[(n^24n+6)/11], {n, 1000}]


PROG

(GAP) List([1..100], n>Int((n^24*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



