A bijective study of basketball walks

zbMATH Open1361.05005arXiv1611.01478MaRDI QIDQ526307FDOQ526307

Jérémie Bettinelli, Éric Fusy, Lucas Randazzo, Cécile Mailler

Publication date: 10 May 2017

Published in: Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Abstract: The Catalan numbers count many classes of combinatorial objects. The most emblematic such objects are probably the Dyck walks and the binary trees, and, whenever another class of combinatorial objects is counted by the Catalan numbers, it is natural to search for an explicit bijection between the latter objects and one of the former objects. In most cases, such a bijection happens to be relatively simple but it might sometimes be more intricate. In this work, we focus on so-called emph{basketball walks}, which are integer-valued walks with step-set $-2,-1,+1,+2$. The presence of $-2$ as an allowed step makes it impossible to use the classical {L}ukasiewicz encoding of trees by integer-valued walks, and thus a different strategy is needed. We give an explicit bijection that maps, for each $nge2$, $n$-step basketball walks from $0$ to $0$ that visit $1$ and are positive except at their extremities to $n$-leaf binary trees. Moreover, we can partition the steps of a walk into $pm1$-steps, odd $+2$-steps or even $-2$-steps, and odd $-2$-steps or even $+2$-steps, and these three types of steps are mapped through our bijection to double leaves, left leaves, and right leaves of the corresponding tree. We also prove that basketball walks from $0$ to $1$ that are positive except at the origin are in bijection with increasing unary-binary trees with associated permutation avoiding $213$. We furthermore give the refined generating function of these objects with an extra variable accounting for the unary nodes.

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

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

Recommendations

• Some more properties of Catalan numbers
• 2-binary trees: bijections and related issues
• Explicit formulas for enumeration of lattice paths: basketball and the kernel method
• scientific article; zbMATH DE number 894188
• Recursive bijections for Catalan objects

zbMATH Keywords

binary treesDyck walks

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05)

Cited In (5)

• The number of [old-time] basketball games with final score \(n\):\(n\) where the home team was never losing but also never ahead by more than \(w\) points
• Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude
• Pseudo-involutions in the Riordan group
• Knight's paths towards Catalan numbers
• Enumerative combinatorics of \textit{XX0} Heisenberg chain

This page was built for publication: A bijective study of basketball walks

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