The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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". 2
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
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.
LINKS
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
FORMULA
a(n) = 2 * A028475(n) for n >= 1. - Sean A. Irvine, Feb 01 2020
EXAMPLE
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]
CROSSREFS
Cf. A028475.
Sequence in context: A089603 A343146 A209358 * A341876 A305406 A296050
KEYWORD
nonn,hard
AUTHOR
Cyril Banderier, Mar 16 2006
EXTENSIONS
More terms a(21)-a(32) from Cyril Banderier, Nov 06 2022
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 14:42 EDT 2024. Contains 372755 sequences. (Running on oeis4.)