A343450 Integers whose nonincreasing digits are at most one more than their position.

1, 2, 11, 21, 22, 31, 32, 111, 211, 221, 222, 311, 321, 322, 331, 332, 411, 421, 422, 431, 432, 1111, 2111, 2211, 2221, 2222, 3111, 3211, 3221, 3222, 3311, 3321, 3322, 3331, 3332, 4111, 4211, 4221, 4222, 4311, 4321, 4322, 4331, 4332, 4411, 4421, 4422, 4431, 4432

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

Table of n, a(n) for n=1..49.

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

Cf. A000108, A009766.

Sequence in context: A081242 A071762 A288945 * A245500 A342945 A266202

Adjacent sequences: A343447 A343448 A343449 * A343451 A343452 A343453

Keyword

nonn,easy,base,fini

Author

Patrick Labarque, Apr 15 2021

Status

approved