اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCounting permutations by their runs up and down
160
0
0.0
(
0
)
تأليف
E. Rodney Canfield
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We find a formula for the number of permutations of $[n]$ that have exactly $s$ runs up and down. The formula is at once terminating, asymptotic, and exact.
قيم البحث
اقرأ أيضاً
Let $G$ be an infinite, vertex-transitive lattice with degree $lambda$ and fix a vertex on it. Consider all cycles of length exactly $l$ from this vertex to itself on $G$. Erasing loops chronologically from these cycles, what is the fraction $F_p/lam
bda^{ell(p)}$ of cycles of length $l$ whose last erased loop is some chosen self-avoiding polygon $p$ of length $ell(p)$, when $ltoinfty$ ? We use combinatorial sieves to prove an exact formula for $F_p/lambda^{ell(p)}$ that we evaluate explicitly. We further prove that for all self-avoiding polygons $p$, $F_pinmathbb{Q}[chi]$ with $chi$ an irrational number depending on the lattice, e.g. $chi=1/pi$ on the infinite square lattice. In stark contrast we current methods, we proceed via purely deterministic arguments relying on Viennots theory of heaps of pieces seen as a semi-commutative extension of number theory. Our approach also sheds light on the origin of the difference between exponents stemming from loop-erased walk and self-avoiding polygon models, and suggests a natural route to bridge the gap between both.
We recall that the $k$-Naples parking functions of length $n$ (a generalization of parking functions) are defined by requiring that a car which finds its preferred spot occupied must first back up a spot at a time (up to $k$ spots) before proceeding
forward down the street. Note that the parking functions are the specialization of $k$ to $0$. For a fixed $0leq kleq n-1$, we define a function $varphi_k$ which maps a $k$-Naples parking function to the permutation denoting the order in which its cars park. By enumerating the sizes of the fibers of the map $varphi_k$ we give a new formula for the number of $k$-Naples parking functions as a sum over the permutations of length $n$. We remark that our formula for enumerating $k$-Naples parking functions is not recursive, in contrast to the previously known formula of Christensen et al [CHJ+20]. It can be expressed as the product of the lengths of particular subsequences of permutations, and its specialization to $k=0$ gives a new way to describe the number of parking functions of length $n$. We give a formula for the sizes of the fibers of the map $varphi_0$, and we provide a recurrence relation for its corresponding logarithmic generating function. Furthermore, we relate the $q$-analog of our formula to a new statistic that we denote $texttt{area}_k$ and call the $k$-Naples area statistic, the specialization of which to $k=0$ gives the $texttt{area}$ statistic on parking functions.
Johnson recently proved Armstrongs conjecture which states that the average size of an $(a,b)$-core partition is $(a+b+1)(a-1)(b-1)/24$. He used various coordinate changes and one-to-one correspondences that are useful for counting problems about sim
ultaneous core partitions. We give an expression for the number of $(b_1,b_2,cdots, b_n)$-core partitions where ${b_1,b_2,cdots,b_n}$ contains at least one pair of relatively prime numbers. We also evaluate the largest size of a self-conjugate $(s,s+1,s+2)$-core partition.
It is known that a sequence Pi_i of permutations is quasirandom if and only if the pattern density of every 4-point permutation in Pi_i converges to 1/24. We show that there is a set S of 4-point permutations such that the sum of the pattern densitie
s of the permutations from S in the permutations Pi_i converges to |S|/24 if and only if the sequence is quasirandom. Moreover, we are able to completely characterize the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight.
We prove that the set of permutations sorted by a stack of depth $t geq 3$ and an infinite stack in series has infinite basis, by constructing an infinite antichain. This answers an open question on identifying the point at which, in a sorting proces
s with two stacks in series, the basis changes from finite to infinite.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
