Fighting Fish: Enumerative Properties

Enrica Duchi ; Veronica Guerrini ; Simone Rinaldi ; Gilles Schaeffer

Séminaire lotharingien de combinatoire, 78B (2017)

Résumé

Fighting fish were very recently introduced by the authors as combinatorial structures made of square tiles that form two dimensional branching surfaces. A main feature of these fighting fish is that the area of uniform random fish of size n scales like n^5/4 as opposed to the typical n^3/2 area behavior of the staircase or directed convex polyominoes that they generalize.

In this extended abstract we focus on enumerative properties of fighting fish: in particular we provide a new decomposition and we show that the number of fighting fish with i left lower free edges and j right lower free edges is equal to

((2i+j-2)! (2j+i-2)!) / (i! j! (2i-1)! (2j-1)!).

These numbers are known to count rooted planar non-separable maps with i+1 vertices and j+1 faces, or two-stack-sortable permutations with respect to ascending and descending runs, or left ternary trees with respect to vertices with even and odd abscissa. However we have been unable until now to provide any explicit bijection between our fish and such structures. Instead we provide new refined generating functions for left ternary trees to prove further equidistribution results.