Pattern-avoiding alternating words

详细信息    查看全文

• 作者：Alice L.L. Gao^a ; ^{gaolulublue@mail.nankai.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Sergey Kitaev^b ; ^{sergey.kitaev@cis.strath.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Philip B. Zhang^c ; ^{zhangbiaonk@163.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Alternating words ; Up-down words ; Down-up words ; Pattern-avoidance ; Narayana numbers ; Fibonacci numbers ; Order ideals ; Bijection
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 July 2016
• 年：2016
• 卷：207
• 期：Complete
• 页码：56-66
• 全文大小：444 K

文摘

A word class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16301275&_mathId=si15.gif&_user=111111111&_pii=S0166218X16301275&_rdoc=1&_issn=0166218X&md5=f777794d6a709c64da49374efb32fe5b" title="Click to view the MathML source">w=w₁w₂⋯w_nclass="mathContainer hidden">class="mathCode">$w=w_1{w}_2\cdots w_n$ is alternating if either class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16301275&_mathId=si16.gif&_user=111111111&_pii=S0166218X16301275&_rdoc=1&_issn=0166218X&md5=b8b3ed45f71f14b42518710d876f0c84" title="Click to view the MathML source">w₁<w₂>w₃<w₄>⋯class="mathContainer hidden">class="mathCode">$w_1<w_2>w_3<w_4>\cdots$ (when the word is up-down) or class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16301275&_mathId=si17.gif&_user=111111111&_pii=S0166218X16301275&_rdoc=1&_issn=0166218X&md5=47c8973494981d3b74a3a57cb3cbcc95" title="Click to view the MathML source">w₁>w₂<w₃>w₄<⋯class="mathContainer hidden">class="mathCode">$w_1>w_2<w_3>w_4<\cdots$ (when the word is down-up). In this paper, we initiate the study of (pattern-avoiding) alternating words. We enumerate up-down (equivalently, down-up) words via finding a bijection with order ideals of a certain poset. Further, we show that the number of 123-avoiding up-down words of even length is given by the Narayana numbers, which is also the case, shown by us bijectively, with 132-avoiding up-down words of even length. We also give formulas for enumerating all other cases of avoidance of a permutation pattern of length 3 on alternating words.