论文标题
下降功能的渐近学
Asymptotics of descent functions
论文作者
论文摘要
1916年，麦克马洪（Macmahon）表明，$ s_n $中的固定下降集$ i $的排列由多项式$ d_i（n）$列举。 Diaz-Lopez，Harris，Insko，Omar和Sagan最近对这种血统多项式恢复了兴趣，并提出了研究此类枚举问题的方向以其他连续模式（后裔是连续模式$ 21 $）。朱研究了连续模式$ 321 $的问题。我们通过研究$ k，k-1，\ ldots（1 $）的任何连续模式的情况来继续进行这项工作，我们称之为$ k $ deScent。在本文中，我们减少了确定以一定$ k $ deScent设置为显式积分的渐近排列数的问题。我们还证明了等均分布定理，表明任何两个稀疏$ k $降低的套件同样可能。 同时在长度$ n $和第一个元素$ m $的情况下计算$ k $ deScent-Descent-Descent-Descent-DeScent的排列数，并获得了一些有用属性的数字Triangle $ f_k（m，n）$。对于$ k = 3 $，$ m = 1 $和$ m = n $对角线是OEIS序列A049774和A080635。对于此数字三角的条目，我们证明了$ k $ th差异的复发关系。这也导致了用于计算$ k $ deScent函数的$ O（n^2）$算法。 在这些结果的过程中，我们证明了一个明确的公式，用于分布$ k $ deScent-Descent-DeScent-Dementing的排列以及第一和最后一个元素的联合分布。我们还对离散订单统计数据有所了解。在我们的方法中，我们结合了代数，分析和概率工具。最后指出了许多开放问题。
In 1916, MacMahon showed that permutations in $S_n$ with a fixed descent set $I$ are enumerated by a polynomial $d_I(n)$. Diaz-Lopez, Harris, Insko, Omar, and Sagan recently revived interest in this descent polynomial, and suggested the direction of studying such enumerative questions for other consecutive patterns (descents being the consecutive pattern $21$). Zhu studied this question for the consecutive pattern $321$. We continue this line of work by studying the case of any consecutive pattern of the form $k,k-1,\ldots,1$, which we call a $k$-descent. In this paper, we reduce the problem of determining the asymptotic number of permutations with a certain $k$-descent set to computing an explicit integral. We also prove an equidistribution theorem, showing that any two sparse $k$-descent sets are equally likely. Counting the number of $k$-descent-avoiding permutations while conditioning on the length $n$ and first element $m$ simultaneously, one obtains a number triangle $f_k(m,n)$ with some useful properties. For $k=3$, the $m=1$ and $m=n$ diagonals are OEIS sequences A049774 and A080635. We prove a $k$th difference recurrence relation for entries of this number triangle. This also leads to an $O(n^2)$ algorithm for computing $k$-descent functions. Along the way to these results, we prove an explicit formula for the distribution of first elements of $k$-descent-avoiding permutations, as well as for the joint distribution of first and last elements. We also develop an understanding of discrete order statistics. In our approach, we combine algebraic, analytic, and probabilistic tools. A number of open problems are stated at the end.
