Enumeration Problems on the Expansion of a Chord Diagram

详细信息    查看全文

• 作者：Tomoki Nakamigawa¹ ; ^{nakami@info.shonan-it.ac.jp" class="auth_mail" title="E-mail the corresponding author}
• 关键词：enumeration ; chord diagram ; expansion ; alternating permutation
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：54
• 期：Complete
• 页码：51-56
• 全文大小：216 K

文摘

A chord diagram is a set of chords of a circle such that no pair of chords has a common endvertex. A pair of chords is called a crossing if the two chords intersect. A chord diagram E is called nonintersecting if E contains no crossing. For a chord diagram E   having a crossing c947fa54c9adc8c6dd889b0" title="Click to view the MathML source">S={x₁x₃,x₂x₄}$S=\{x_1{x}_3,x_2{x}_4\}$, the expansion of E with respect to S is to replace E   with E₁=(E\S)∪{x₂x₃,x₄x₁}$E_1=(E\backslash S)\cup \{x_2{x}_3,x_4{x}_1\}$ or E₂=(E\S)∪{x₁x₂,x₃x₄}$E_2=(E\backslash S)\cup \{x_1{x}_2,x_3{x}_4\}$ chord diagram c93ef74e62f7c4bd028d" title="Click to view the MathML source">E=E₁∪E₂$E=E_1\cup E_2$ is called complete bipartite of type (m, n  ), denoted by C_m,n$C_{m,n}$, if (1) both c9931a9477a10d2bb59fbc33ec" title="Click to view the MathML source">E₁$E_1$ and E₂$E_2$ are nonintersecting, (2) for every pair e₁∈E₁$e_1\in E_1$ and e₂∈E₂,e₁$e_2\in E_2,e_1$ and e₂$e_2$ are crossing, and (3) |E₁|=m$|E_1|=m$, |E₂|=n$|E_2|=n$. Let f_m,n$f_{m,n}$ be the cardinality of the multiset of all nonintersecting chord diagrams generated from C_m,n$C_{m,n}$ with a finite sequence of expansions. In this paper, it is shown ∑_m,nf_m,n(x^m/m!)(yⁿ/n!)${\sum }_{m,n}{f}_{m,n}(x^m/m!)(y^n/n!)$ is 1/(coshxcoshy−(sinhx+sinhy))$1/(\cosh x\cosh y-(\sinh x+\sinh y))$.