cp's OEIS Frontend

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

%I A116456 #42 Jan 21 2023 09:16:07
%S A116456 1,2,8,40,228,1424,9520,67064,492292,3735112,29114128,232077344,
%T A116456 1885195276,15562235264,130263211680,1103650297320,9450760284100,
%U A116456 81696139565864,712188311673280,6255662512111248,55324571848957688,492328039660580784,4406003100524940624,39635193868649858744,358245485706959890508
%N A116456 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 A116456 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 A116456 These objects were considered by Guitter et al., 1999.
%H A116456 Olivier Golinelli, <a href="/A116456/b116456.txt">Table of n, a(n) for n = 0..34</a>
%H A116456 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 A116456 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 A116456 a(n) = 2 * A028475(n) for n >= 1. - _Sean A. Irvine_, Feb 01 2020
%e A116456 a(4)=228. Here are the 228 words of length 8:
%e A116456 [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 A116456 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 A116456 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 A116456 aabbcdab, ababacdb, ababcdab, abaabbab, aaababbb, abababab, ababaabb, aaabbbab, aaabbabb, abaababb, aababbab, aabababb, aabaabbb, aabbabab, abaaabbb, aabbaabb, aaaabbbb]
%Y A116456 Cf. A028475.
%K A116456 nonn,hard
%O A116456 0,2
%A A116456 _Cyril Banderier_, Mar 16 2006
%E A116456 More terms a(21)-a(32) from _Cyril Banderier_, Nov 06 2022