A Bijective Study of Basketball Walks

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

Séminaire lotharingien de combinatoire, Tome 77 (2017-2018)

Résumé

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 paper, we focus on so-called basketball walks, which are integer-valued walks with step-set {-2,-1,+1,+2}. We give an explicit bijection that maps, for each n >= 2, 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 +-1-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.