OFFSET
1,2
COMMENTS
Enumeration of the different triangulated planar polygons (TPP) on a base through hierarchic ear addition. An ear of a polygon is a triangle with two edges on the boundary. Start with a triangle on base 0, and number the two other edges 1 and 2 in counterclockwise direction. Add an ear on edge 1 or 2. The two different quadrilaterals on base 0 have now three other edges and we add a new ear on one of the renumbered edges 1, 2 or 3 but only where it forms a nonincreasing sequence with the preceding ear additions. We now have 1 and 2 for the two quadrilaterals and 11, 21, 22, 31, 32 for the five different pentagons. We can continue for the next polygons. Each generated number with v-3 digits stands for one triangulated planar polygon with v edges and vice versa and we don't have duplicates. However the decimal numbering limits the last generation to 98765432, for an 11-gon (4 <= v <= 11). The starting triangle (a degenerate TPP3) can also be seen as an ear addition on the base 0 (v >= 3).
LINKS
Tom Davis, Catalan Numbers, 2016.
F. Hurtado and M. Noy, Graph of triangulations of a convex polygon and tree of triangulations, 1999.
Richard P. Stanley, Catalan Addendum, 2013.
EXAMPLE
'1' and '2' are the 2 triangulated planar polygons on 4 vertices (TPP4). '11, 21, 22, 31, 32' are the 5 TPP5. The next group with 3 digits gives the 14 TPP6, and so on, following the Catalan numbers 2, 5, 14, 42, ... (see A000108).
Additionally, the numbers of d-digit terms with the same starting digit reflect the numbers in the d-th row of Catalan's triangle, A009766 (e.g., 1 two-digit number starting with '1', 2 starting with '2' and 2 starting with '3').
The 1111...'s are fan-TPP's with the top in vertex 1 (between edge 0 and 1), and 98765432 is also, but with the top in the last vertex.
MATHEMATICA
okQ[digits_List] := AllTrue[MapIndexed[#1 <= #2[[1]]+1&, Reverse[digits]], #&];
row[n_] := Module[{i, iter}, i[0] = n+1; iter = Table[{i[k+1], i[k]}, {k, 0, n-1}]; Table[Array[i, n], Evaluate[Sequence @@ iter]] // Flatten[#, n-1]&];
T[n_] := FromDigits /@ Select[row[n], okQ];
Table[T[n], {n, 1, 4}] // Flatten (* Jean-François Alcover, May 08 2021 *)
CROSSREFS
KEYWORD
nonn,easy,base,fini
AUTHOR
Patrick Labarque, Apr 15 2021
STATUS
approved