Patrick Labarque - cp's OEIS frontend

User: Patrick Labarque

Patrick Labarque has authored 2 sequences.

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

Patrick Labarque, Apr 15 2021

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

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

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.

Cf. A000108, A009766.

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

A174395 The number of different 4-colorings for the vertices of all triangulated planar polygons on a base with n vertices if the colors of two adjacent boundary vertices are fixed.

Original entry on oeis.org

0, 2, 10, 40, 140, 462, 1470, 4580, 14080, 42922, 130130, 393120, 1184820, 3565382, 10717990, 32197660, 96680360, 290215842, 870997050, 2613690200, 7842468700, 23530202302, 70596199310, 211799782740, 635421717840, 1906309892762, 5719019156770, 17157236427280

Offset: 3

Patrick Labarque, Mar 18 2010, Mar 21 2010

1st: The number of different vertex colorings with 4 or 3 colors for n vertices is: (3^(n-1)-2-(-1)^n)/4.
2nd: The number of 3-colorings is: (2^n -3-(-1)^n)/3.
The above sequence is the difference between the first and the second one.

			n=3 then a(3)=0 as there are no 4-colorings for the only triangle.
n=4 then a(4)=2 as there are six good colorings less four 3-colorings for the two triangulated quadrilaterals (4-gons).
n=5 then a(5)=10 as there are twenty good colorings less ten 3-colorings for the five triangulated pentagons.

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
Index entries for linear recurrences with constant coefficients, signature (5,-5,-5,6).

Equals A081251 (2,6,20...) minus A026644 (2,4,10...)

[(3^n - 2^(n+2) + 6 + (-1)^n) / 12: n in [3..30]]; // Vincenzo Librandi, Sep 23 2013

CoefficientList[Series[-2 x/((x - 1) (x + 1) (2 x - 1) (3 x - 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 23 2013 *)
LinearRecurrence[{5,-5,-5,6},{0,2,10,40},30] (* Harvey P. Dale, Aug 29 2015 *)

Vec(-2*x^4/((x-1)*(x+1)*(2*x-1)*(3*x-1))  + O(x^100)) \\ Colin Barker, Sep 22 2013

a(n) = (3^n - 2^(n+2) + 6 + (-1)^n) / 12.

a(n) = 5*a(n-1)-5*a(n-2)-5*a(n-3)+6*a(n-4). G.f.: -2*x^4 / ((x-1)*(x+1)*(2*x-1)*(3*x-1)). - Colin Barker, Sep 22 2013

More terms from Colin Barker, Sep 22 2013

cp's OEIS Frontend

User: Patrick Labarque

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica