Bijection between increasing binary trees and rook placements on double staircases

DOI10.37236/10926MaRDI QIDQ2111784zbMATH OpenOpenAlexFDO

Authors Bishal Deb

Publication date 17 January 2023

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

Copyright license Creative Commons Attribution 4.0 International

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 pathsgrowth diagramstableauxYoung's lattice

Mathematics Subject Classification ID

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

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

Review text

Summary: In this paper, we shall construct a bijection between rook placements on double staircases (introduced by \textit{M. Josuat-Vergès} [Discrete Math. Theor. Comput. Sci. 19, No. 3, Paper No. 3, 22 p. (2017; Zbl 1401.05305)]) 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 \textit{V. Tewari} [J. Comb. Theory, Ser. A 163, 98--117 (2019; Zbl 1403.05068)].

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)