A116456 - OEIS

%I #42 Jan 21 2023 09:16:07

%S 1,2,8,40,228,1424,9520,67064,492292,3735112,29114128,232077344,

%T 1885195276,15562235264,130263211680,1103650297320,9450760284100,

%U 81696139565864,712188311673280,6255662512111248,55324571848957688,492328039660580784,4406003100524940624,39635193868649858744,358245485706959890508

%N a(n) is the number of words of length 2n in the language F, the language of "parity-constrained-shuffle of well-parenthesized words".

%C More precisely: Take a Dyck word on the alphabet {a,b} and a Dyck word on the alphabet {c,d}. I.e., you have 2 words with well-balanced parentheses (a/b and c/d are considered as 2 sets of parentheses). Make a shuffle of these 2 words, with the constraint that each "a" at an even (resp. odd) position is closed by a "b" at an odd (resp. even) position. Impose the similar constraint for "c" and "d". F is the language of all such "parity-constrained" shuffles of 2 Dyck Languages. a(n) is also related to the number of ways of linking (without any crossing) even and odd integers (from 1 to 2n).

%C These objects were considered by Guitter et al., 1999.

%H Olivier Golinelli, <a href="/A116456/b116456.txt">Table of n, a(n) for n = 0..34</a>

%H Philippe Di Francesco, Bertrand Duplantier, Olivier Golinelli, and Emmanuel Guitter, <a href="https://arxiv.org/abs/2210.08887">Exponents for Hamiltonian paths on random bicubic maps and KPZ</a>, arXiv:2210.08887 [math-ph], 2022.

%H E. Guitter, C. Kristjansen, and J. L. Nielsen, <a href="http://arxiv.org/abs/cond-mat/9811289">Hamiltonian Cycles on Random Eulerian Triangulations</a>, arXiv:cond-mat/9811289 [cond-mat.stat-mech], 1998; Nucl. Phys. B546 (1999), 731-750. doi:10.1016/S0550-3213(99)00058-9

%F a(n) = 2 * A028475(n) for n >= 1. - _Sean A. Irvine_, Feb 01 2020

%e a(4)=228. Here are the 228 words of length 8:

%e [cdccddcd, cccdcddd, cdcdcdcd, cdcdccdd, cccdddcd, cccddcdd, cdccdcdd, ccdcddcd, ccdcdcdd, ccdccddd, ccddcdcd, cdcccddd, ccddccdd, ccccdddd, ccddabcd, ccddacdb, ccddcdab, ccddcabd, ccdabdcd, ccabddcd, cabcddcd, cacdbdcd, abcccddd, acccdddb, abccdcdd, accdcddb, cdcdabcd, cdcdacdb, cdcdcdab, cdcdcabd, cdcabdcd, cdacdcdb, cdacdbcd, cdabcdcd, cabdcdcd, cabdccdd, cdabccdd, cdaccddb, ccabdcdd, ccdabcdd, ccdacdbd, ccdcabdd, ccdcddab, ccdcdabd, cabcdcdd, cacdbcdd, cacdcdbd, cdccabdd, cdccddab, cdccdabd, caccddbd, cabccddd, ccacdbdd, ccabcddd, cccabddd, cccdabdd,

%e cccdddab, cccddabd, abccddcd, accddbcd, accddcdb, abcdccdd, acdbccdd, acdccddb, abcdcdcd, acdbcdcd, acdcdcdb, acdcdbcd, cdcabcdd, cdcacdbd, cdcdaabb, cdaacdbb, caacdbbd, caabbcdd, caabcdbd, cacdabbd, ccddaabb, ccaabbdd, ccaaddbb, abcdcdab, acdbabcd, acdbacdb, acdbcdab, acdcdbab, acdbcabd, acdcdabb, acdabbcd, acdabcdb, acdacdbb, acdcabdb, acabdbcd, abcabdcd, abcdcabd, cdacdbab, cdabcabd, cdababcd, cdabacdb, cdabcdab, cababdcd, ababcdcd, abacdbcd, abacdcdb, abcdabcd, abcdacdb, accbaddb, accddbab, cabdcdab, cabdcabd, acabdcdb, aacdbcdb, aacdcdbb, aabbcdcd,

%e aabcdbcd, aabcdcdb, cababcdd, cabacdbd, cabcabdd, aacdbbcd, caabbdcd, cabcddab, cabcdabd, ccababdd, ccabddab, ccabdabd, cacdbdab, cacdbabd, accabddb, aaccddbb, aabbccdd, aabccddb, accdabdb, accddabb, acacdbdb, acabcddb, cdcabdab, cdcababd, cdcdabab, cabdabcd, cabdacdb, ccdaabbd, cacabdbd, aaccbbdd, abaccddb, ccdabdab, ccdababd, ccddabab, abcabcdd, abcacdbd, abccabdd, abccddab, abccdabd, ababccdd, caadcbbd, cdacdabb, cdaabbcd, cdaabcdb, cdacabdb, cdcaabbd, acdbabab, caababbd, cabdaabb, abcabdab, abcababd, aabcabdb, aabacdbb, cdaaabbb, caabbdab, caabbabd, cdaabbab, acababdb, acabdabb, acdababb, aabcdabb, aababbcd, aacdbabb, aababcdb, abcdabab, abacdbab, ababcabd, abababcd, cabaabbd, caaabbbd, aacdabbb, aaacdbbb, aaabbbcd, aacabdbb, aaabbcdb, aaabcdbb, abacdabb, abaabbcd, abaabcdb, abaacdbb, abacabdb, abcaabbd, abcdaabb, acdbaabb, cdaababb, cababdab, cabababd, cabdabab, cdababab, cdabaabb, acdaabbb, acaabbdb, acdabbab, aacdbbab, acabdbab, aabcdbab, aabbcabd, aabbabcd, aabbacdb,

%e aabbcdab, ababacdb, ababcdab, abaabbab, aaababbb, abababab, ababaabb, aaabbbab, aaabbabb, abaababb, aababbab, aabababb, aabaabbb, aabbabab, abaaabbb, aabbaabb, aaaabbbb]

%Y Cf. A028475.

%K nonn,hard

%O 0,2

%A _Cyril Banderier_, Mar 16 2006

%E More terms a(21)-a(32) from _Cyril Banderier_, Nov 06 2022