ترغب بنشر مسار تعليمي؟ اضغط هنا

A combinatorial bijection on di-sk trees

130   0   0.0 ( 0 )
 نشر من قبل Zhicong Lin
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

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.



قيم البحث

اقرأ أيضاً

132 - Yidong Sun 2008
In this short note, we first present a simple bijection between binary trees and colored ternary trees and then derive a new identity related to generalized Catalan numbers.
103 - David Callan 2016
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.
117 - David Callan 2016
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.
451 - Loic Foissy 2007
We consider the combinatorial Dyson-Schwinger equation X=B^+(P(X)) in the non-commutative Connes-KreimerHopf algebra of planar rooted trees H, where B^+ is the operator of grafting on a root, and P a formal series. The unique solution X of this equat ion generates a graded subalgebra A_P ofH. We describe all the formal series P such that A_P is a Hopf subalgebra. We obtain in this way a 2-parameters family of Hopf subalgebras of H, organized into three isomorphism classes: a first one, restricted to a olynomial ring in one variable; a second one, restricted to the Hopf subalgebra of ladders, isomorphic to the Hopf algebra of quasi-symmetric functions; a last (infinite) one, which gives a non-commutative version of the Fa`a di Bruno Hopf algebra. By taking the quotient, the last classe gives an infinite set of embeddings of the Fa`a di Bruno algebra into the Connes-Kreimer Hopf algebra of rooted trees. Moreover, we give an embedding of the free Fa`a di Bruno Hopf algebra on D variables into a Hopf algebra of decorated rooted trees, togetherwith a non commutative version of this embedding.
139 - Heesung Shin 2008
In 1980, G. Kreweras gave a recursive bijection between forests and parking functions. In this paper we construct a nonrecursive bijection from forests onto parking functions, which answers a question raised by R. Stanley. As a by-product, we obtain a bijective proof of Gessel and Seos formula for lucky statistic on parking functions.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا