اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA note on a bijection for Schroder permutations
104
0
0.0
(
0
)
تأليف
David Callan
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
There is a bijection from Schroder paths to {4132, 4231}-avoiding permutations due to Bandlow, Egge, and Killpatrick that sends area to inversion number. Here we give a concise description of this bijection.
قيم البحث
اقرأ أيضاً
A di-sk tree is a rooted binary tree whose nodes are labeled by $oplus$ or $ominus$, and no node has the same label as its right child. The di-sk trees are in natural bijection with separable permutations. We construct a combinatorial bijection on di
-sk trees proving the two quintuples $(LMAX,LMIN,DESB,iar,comp)$ and $(LMAX,LMIN,DESB,comp,iar)$ have the same distribution over separable permutations. Here for a permutation $pi$, $LMAX(pi)/LMIN(pi)$ is the set of values of the left-to-right maxima/minima of $pi$ and $DESB(pi)$ is the set of descent bottoms of $pi$, while $comp(pi)$ and $iar(pi)$ are respectively the number of components of $pi$ and the length of initial ascending run of $pi$. Interestingly, our bijection specializes to a bijection on $312$-avoiding permutations, which provides (up to the classical {em Knuth--Richards bijection}) an alternative approach to a result of Rubey (2016) that asserts the two triples $(LMAX,iar,comp)$ and $(LMAX,comp,iar)$ are equidistributed on $321$-avoiding permutations. Rubeys result is a symmetric extension of an equidistribution due to Adin--Bagno--Roichman, which implies the class of $321$-avoiding permutations with a prescribed number of components is Schur positive. Some equidistribution results for various statistics concerning tree traversal are presented in the end.
We show that sequences A026737 and A111279 in The On-Line Encyclopedia of Integer Sequences are the same by giving a bijection between two classes of Grand Schroder paths.
In this paper we present a simple framework to study various distance problems of permutations, including the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. These problems are ver
y important in the study of the evolution of genomes. We give a general formulation for lower bounds of the transposition and block-interchange distance from which the existing lower bounds obtained by Bafna and Pevzner, and Christie can be easily derived. As to the reversal distance of signed permutations, we translate it into a block-interchange distance problem of permutations so that we obtain a new lower bound. Furthermore, studying distance problems via our framework motivates several interesting combinatorial problems related to product of permutations, some of which are studied in this paper as well.
In this paper, we compute the distribution of the first letter statistic on nine avoidance classes of permutations corresponding to two pairs of patterns of length four. In particular, we show that the distribution is the same for each class and is g
iven by the entries of a new Schroder number triangle. This answers in the affirmative a recent conjecture of Lin and Kim. We employ a variety of techniques to prove our results, including generating trees, direct bijections and the kernel method. For the latter, we make use of in a creative way what we are trying to show in three cases to aid in solving a system of functional equations satisfied by the associated generating functions.
A permutation is centrosymmetric if it is fixed by a half-turn rotation of its diagram. Initially motivated by a question by Alexander Woo, we investigate the question of whether the growth rate of a permutation class equals the growth rate of its ev
en-size centrosymmetric elements. We present various examples where the latter growth rate is strictly less, but we conjecture that the reverse inequality cannot occur. We conjecture that equality holds if the class is sum closed, and we prove this conjecture in the special case where the growth rate is at most $xi approx 2.30522$, using results from Pantone and Vatter on growth rates less than $xi$. We prove one direction of inequality for sum closed classes and for some geometric grid classes. We end with preliminary findings on new kinds of growth-rate thresholds that are a little bit larger than $xi$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
