1,2

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).

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.

'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.

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 *)

Cf. A000108, A009766.

Sequence in context: A081242 A071762 A288945 * A245500 A342945 A266202

Adjacent sequences: A343447 A343448 A343449 * A343451 A343452 A343453

nonn,easy,base,fini

Patrick Labarque, Apr 15 2021

approved