关于路径图与Stirling置换

摘要翻译：
置换可以根据四种局部类型进行局部分类：高峰、低谷、双升和双降。二叉增树的相应分类使用四种不同类型的节点。Flajolett使用置换之间的经典双射、二值递增树和适当定义的由Motzkin路径诱导的路径图，证明了局部类型生成函数的连分式表示。本文的目的是将局部类型的概念从置换扩展到$K$-Stirling置换（也称为$K$-多重置换）。我们将这些局部类型建立到$(k+1)$-ary递增树的nodetypes的双射。利用由L ukasiewicz路径诱导的路径图，给出了这些局部类型的母函数的分支连续分数表示，将其从置换推广到任意的$k$-Stirling置换。利用非标准增树、$K$-Stirling置换和路径图之间的对应关系，进一步证明了普通Stirling置换的母函数至少有三个分支连分式表示。
---
英文标题：
On Path diagrams and Stirling permutations
---
作者：
Markus Kuba and Anna L. Varvak
---
发布时间：
2021
---
英文摘要：
  A permutation can be locally classified according to the four local types:peaks, valleys, double rises and double falls. The corresponding classificationof binary increasing trees uses four different types of nodes. Flajoletdemonstrated the continued fraction representation of the generating functionof local types, using a classical bijection between permutations, binaryincreasing trees, and suitably defined path diagrams induced by Motzkin paths.  The aim of this article is to extend the notion of local types frompermutations to $k$-Stirling permutations (also known as$k$-multipermutations). We establish a bijection of these local types to nodetypes of $(k+1)$-ary increasing trees. We present a branched continued fractionrepresentation of the generating function of these local types through abijection with path diagrams induced by \L ukasiewicz paths, generalizing theresults from permutations to arbitrary $k$-Stirling permutations.  We further show that the generating function of ordinary Stirling permutationhas at least three branched continued fraction representations, usingcorrespondences between non-standard increasing trees, $k$-Stirlingpermutations and path diagrams.
---
PDF链接：
https://arxiv.org/pdf/0906.1672