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".

1, 2, 8, 40, 228, 1424, 9520, 67064, 492292, 3735112, 29114128, 232077344, 1885195276, 15562235264, 130263211680, 1103650297320, 9450760284100, 81696139565864, 712188311673280, 6255662512111248, 55324571848957688, 492328039660580784, 4406003100524940624, 39635193868649858744, 358245485706959890508

Offset: 0

Author

Cyril Banderier, Mar 16 2006

Keywords

• nonn
• hard

Comments

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).

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

Examples

			a(4)=228. Here are the 228 words of length 8:
[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,
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,
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,
aabbcdab, ababacdb, ababcdab, abaabbab, aaababbb, abababab, ababaabb, aaabbbab, aaabbabb, abaababb, aababbab, aabababb, aabaabbb, aabbabab, abaaabbb, aabbaabb, aaaabbbb]
		

Links

• Olivier Golinelli, Table of n, a(n) for n = 0..34
• Philippe Di Francesco, Bertrand Duplantier, Olivier Golinelli, and Emmanuel Guitter, Exponents for Hamiltonian paths on random bicubic maps and KPZ, arXiv:2210.08887 [math-ph], 2022.
• E. Guitter, C. Kristjansen, and J. L. Nielsen, Hamiltonian Cycles on Random Eulerian Triangulations, arXiv:cond-mat/9811289 [cond-mat.stat-mech], 1998; Nucl. Phys. B546 (1999), 731-750. doi:10.1016/S0550-3213(99)00058-9

Crossrefs

Cf. A028475.

Formula

a(n) = 2 * A028475(n) for n >= 1. - Sean A. Irvine, Feb 01 2020

Extensions

More terms a(21)-a(32) from Cyril Banderier, Nov 06 2022