Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA combinatorial bijection on di-sk trees
130
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
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.
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 equation 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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
