Two-Dimensional Catalan Numbers

The Catalan number, C(n), is the number of ways a polygon with n sides can be triangulated with no additional vertices. These numbers can be calculated recursively. We generalize the problem to the next higher dimension. Given a triangulation T of the 2-sphere, define the Catalan number of T to be the number of non-degenerate ``triangulations'' of the ball with tetrahedra that have boundary isomorphic to T and which only use vertices in T.

Question: How do you compute the Catalan number of a triangulation of the 2-sphere?

The smallest example is the complete graph K(4). This is trivial as there is only one such decomposition into tetrahedra. The next smallest example is K(5)-K(2). The problem generalizes to even higher dimensions.

Submitted by: Steve Fisk, Department of Mathematics, Bowdoin College, Brunswick ME 04011-2599 USA.

Send comments to

August, 1995