Séminaire Lotharingien de Combinatoire, 78B.43 (2017), 12 pp.

Enrica Duchi, Veronica Guerrini, Simone Rinaldi and Gilles Schaeffer

Fighting Fish: Enumerative Properties

Abstract. 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 n5/4 as opposed to the typical n3/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.

Received: November 14, 2016. Accepted: February 17, 2017. Final version: April 1, 2017.

The following versions are available: