Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCounting permutations by their runs up and down
160
0
0.0
(
0
)
Authors
E. Rodney Canfield
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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/lambda^{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 simultaneous 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 densities 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 process with two stacks in series, the basis changes from finite to infinite.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
