%I #11 Mar 31 2012 10:24:26
%S 1,2,6,26,162,1450,18626,343210,9069306,343611106,18662952122,
%T 1453016097506
%N Gog words avoiding the subpattern 312
%C Gog words of size n are words of length n in an alphabet
%C of odd-sized tuples of increasing integers
%C that satisfy the following conditions:
%C (1) The length of the word is n,
%C (2) Each letter in the word has maximum entry at most n,
%C (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,
%C (4) Every repeated integer alternates in odd and even numbered positions in subsequent tuples.
%C They are in natural bijection with alternating sign matrices.
%C 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
%C (1) c, a, b appear in odd positions in x_i, x_j , x_k respectively where i<j<k,
%C (2) b is not in an even position in x_{i+1},..., x_{k-1},
%C (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.
%C (4) a < b < c.
%H Arvind Ayyer, Robert Cori, Dominique Gouyou-Beauchamps,
%H <a href="http://arxiv.org/abs/1101.1666">Monotone triangles and 312 pattern avoidance</a>, arXiv:1101.1666
%e 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.
%e More complicated examples: 31(234)3 and 25(12356)542 contain the subpattern 312 but 25(12456)532 does not.
%Y Cf. A005130, A000108, A116715, A116722, A116735
%K nonn,hard
%O 1,2
%A _Arvind Ayyer_, Jan 18 2011
|