Bijection between increasing binary trees and rook placements on double staircases

DOI10.37236/10926MaRDI QIDQ2111784zbMATHOpenAlexFDO

Authors Bishal Deb

Publication date 17 January 2023

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

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

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

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)

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).

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

Cites work

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

Cited in

(1)

• Bijections on m-level Rook Placements

Describes a project that uses

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)