A180349 Gog words avoiding the subpattern 312.

1, 2, 6, 26, 162, 1450, 18626, 343210, 9069306, 343611106, 18662952122, 1453016097506, 162144482866166, 25932885879826066

Offset: 1

Author

Arvind Ayyer, Jan 18 2011

Keywords

• nonn
• hard

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

Examples

			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.
		

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.

Crossrefs

Cf. A005130, A000108, A116715, A116722, A116735.

Extensions

a(13)-a(14) from Ludovic Schwob, May 18 2024