A321195 Minimum number of monochromatic Schur triples over all 2-colorings of [n].

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

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

Sequence in context: A085680 A253186 A160138 * A249020 A258470 A248357

Adjacent sequences: A321192 A321193 A321194 * A321196 A321197 A321198

Keyword

nonn

Author

Elaine Wong, Dec 18 2018

Status

approved