OFFSET
1,2
COMMENTS
Gog words of size n are words of length n in an alphabet of odd-sized tuples of increasing integers that satisfy the following conditions:
(1) The length of the word is n,
(2) each letter in the word has maximum entry at most n,
(3) an integer in an even-numbered position in a tuple is repeated in another tuple to its left and to its right in odd-numbered positions,
(4) every repeated integer alternates in odd- and even-numbered positions in subsequent tuples.
They are in natural bijection with alternating sign matrices.
Further, the integers c, a, b form a 312-subpattern of the Gog word w = x_1 x_2 ... x_n if the following conditions hold:
(1) c, a, b appear in odd positions in x_i, x_j, x_k, respectively, where i < j < k,
(2) b is not in an even position in x_(i+1), ..., x_(k-1),
(3) if x_j = (p_1, q_1, ..., p_(k-1), q_(k-1), p_k), either b > p_k or p_l < b < q_l for some l.
(4) a < b < c.
a(n) is equal to the number of gapless Gog triangles of size n, and also to the number of gapless Magog triangles of size n. - Ludovic Schwob, May 18 2024
LINKS
Arvind Ayyer, Robert Cori, and Dominique Gouyou-Beauchamps, Monotone triangles and 312 pattern avoidance, arXiv:1101.1666 [math.CO], 2011.
Mathilde Bouvel, Rebecca Smith, and Jessica Striker, Key-avoidance for alternating sign matrices, arXiv:2408.05311 [math.CO], 2024. See p. 4.
Ludovic Schwob, Sage program.
EXAMPLE
For n=3, there are 7 Gog words: (1)(2)(3), (1)(3)(2), (2)(1)(3), (2)(3)(1), (3)(1)(2), (3)(2)(1) and (2)(123)(2). Of these, all but (3)(1)(2) avoid the subpattern 312.
More complicated examples: 31(234)3 and 25(12356)542 contain the subpattern 312 but 25(12456)532 does not.
CROSSREFS
KEYWORD
nonn,hard
AUTHOR
Arvind Ayyer, Jan 18 2011
EXTENSIONS
a(13)-a(14) from Ludovic Schwob, May 18 2024
STATUS
approved