login
A343450
Integers whose nonincreasing digits are at most one more than their position.
0
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).
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
Sequence in context: A081242 A071762 A288945 * A245500 A342945 A266202
KEYWORD
nonn,easy,base,fini
AUTHOR
Patrick Labarque, Apr 15 2021
STATUS
approved