Bijection between increasing binary trees and rook placements on double staircases

DOI10.37236/10926zbMATH Open1506.05214arXiv2112.04872OpenAlexW4316038206MaRDI QIDQ2111784FDOQ2111784

Authors: Bishal Deb 

Publication date: 17 January 2023

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: In this paper, we shall construct a bijection between rook placements on double staircases (introduced by Josuat-Verg`es in 2017) and increasing binary trees. We introduce two subclasses of rook placements on double staircases, which we call left and right-aligned rook placements. We show that their enumeration, while keeping track of a certain statistic, gives the $gamma$-vectors of the Eulerian polynomials. We conclude with a discussion on a different bijection that fits in very well with our main bijection, and another discussion on generalising our main bijection. Our main bijection is a special case of a bijection due to Tewari (2019).

Full work available at URL: https://arxiv.org/abs/2112.04872

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Bijections on m-level Rook Placements
• Bijections on \(m\)-level rook placements
• A bijection from staircase tableaux to inversion tables, giving some Eulerian and Mahonian statistics
• 2-binary trees: bijections and related issues
• A bijection of plane increasing trees with relaxed binary trees of right height at most one

zbMATH Keywords

Dyck pathstableauxYoung's latticegrowth diagrams

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Combinatorial aspects of representation theory (05E10) Combinatorial identities, bijective combinatorics (05A19)

Cites Work

• Generalized Stirling permutations, families of increasing trees and urn models
• The \(r\)-multipermutations
• Théorie géométrique des polynômes eulériens
• Analysis of Statistics for Generalized Stirling Permutations
• Eulerian Numbers
• Bijections between oscillating tableaux and (semi)standard tableaux via growth diagrams
• Permutations selon leurs pics, creux, doubles montees et double descentes, nombres d'Euler et nombres de Genocchi
• Generalized Robinson-Schensted-Knuth correspondence
• Gessel polynomials, rooks, and extended linial arrangements

Cited In (1)

• Bijections on m-level Rook Placements

Uses Software

• OEIS

This page was built for publication: Bijection between increasing binary trees and rook placements on double staircases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111784)