A topologist came to me with this question, but everything I think should work doesn't.

How many triangulations are there of a polyhedron with n vertices?

By a "triangulation" of a polyhedron P we mean a decomposition of P into 3-simplices whose interiors are disjoint, whose vertices are vertices of P, and whose union is P. Since this obviously depends on the polyhedron, let's say that P is the convex hull of n points on the curve (t, t^2, t^3). (I think this is general, but a proof of that would be nice too.) In particular, this means that all of the faces are triangles, since no four vertices are coplanar.

Since triangulations of a polygon are counted by the Catalan numbers, a reasonable first guess is that these are counted by the generalized Catalan numbers $C_{n,k} = \frac{1}{(k-1)(n+1)} {kn \choose n}$, which count k-ary trees (among other things). But just at n=5 we run into trouble: there are 2 (not 3) such triangulations, and *they don't even contain a fixed number of pieces*: one of them triangulates P into two tetrahedra, and one breaks it into three.

This seems obvious enough that someone would have asked it before, but I'm not finding anything. Of course, answers to the obvious generalization (triangulations of k-polytopes whose vertices lie on (t, t^2, ..., t^k)) are welcome as well.