ﻻ يوجد ملخص باللغة العربية
Recall that an excedance of a permutation $pi$ is any position $i$ such that $pi_i > i$. Inspired by the work of Hopkins, McConville and Propp (Elec. J. Comb., 2017) on sorting using toppling, we say that a permutation is toppleable if it gets sorted by a certain sequence of toppling moves. One of our main results is that the number of toppleable permutations on $n$ letters is the same as those for which excedances happen exactly at ${1,dots, lfloor (n-1)/2 rfloor}$. Additionally, we show that the above is also the number of acyclic orientations with unique sink (AUSOs) of the complete bipartite graph $K_{lceil n/2 rceil, lfloor n/2 rfloor + 1}$. We also give a formula for the number of AUSOs of complete multipartite graphs. We conclude with observations on an extremal question of Cameron et al. concerning maximizers of (the number of) acyclic orientations, given a prescribed number of vertices and edges for the graph.
We consider several generalizations of the classical $gamma$-positivity of Eulerian polynomials (and their derangement analogues) using generating functions and combinatorial theory of continued fractions. For the symmetric group, we prove an expansion formula for
This paper develops an analogy between the cycle structure of, on the one hand, random permutations with cycle lengths restricted to lie in an infinite set $S$ with asymptotic density $sigma$ and, on the other hand, permutations selected according to
In this note we investigate correlation inequalities for `up-sets of permutations, in the spirit of the Harris--Kleitman inequality. We focus on two well-studied partial orders on $S_n$, giving rise to differing notions of up-sets. Our first result s
We introduce a new boundedness condition for affine permutations, motivated by the fruitful concept of periodic boundary conditions in statistical physics. We study pattern avoidance in bounded affine permutations. In particular, we show that if $tau
We study the number of acyclic orientations on the generalized two-dimensional Sierpinski gasket $SG_{2,b}(n)$ at stage $n$ with $b$ equal to two and three, and determine the asymptotic behaviors. We also derive upper bounds for the asymptotic growth