A350116 Number of ways to partition the set of vertices of a convex {n+8}-gon into 3 non-intersecting polygons.

0, 12, 45, 110, 220, 390, 637, 980, 1440, 2040, 2805, 3762, 4940, 6370, 8085, 10120, 12512, 15300, 18525, 22230, 26460, 31262, 36685, 42780, 49600, 57200, 65637, 74970, 85260, 96570, 108965, 122512, 137280, 153340, 170765, 189630, 210012, 231990, 255645, 281060, 308320

Offset: 0

Author

Janaka Rodrigo, Dec 21 2021

Keywords

• easy
• nonn

Comments

Equivalently, the number of noncrossing set partitions of an {n+8}-set into 3 blocks with 3 or more elements in each block.

Examples

			The a(1) = 12 solutions are:
   {123}{456}{789}, {234}{567}{891}, {345}{678}{912},
   {156}{234}{567}, {267}{345}{891}, {378}{456}{912},
   {489}{567}{123}, {591}{678}{234}, {612}{789}{345},
   {723}{891}{456}, {834}{912}{567}, {945}{123}{678}.
In the above, the numbers can be considered to be the partition of a 9-set into 3 blocks or the partition of the vertices of a convex 9-gon into 3 triangles (with the vertices labeled 1..9 in order).
a(2) = 45 corresponding to the number of ways to partition the vertices of a 10-gon into two triangles and one quadrilateral.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Crossrefs

Column k=3 of A350248.

The case of any number of parts for an n-gon is A114997.

The case of exactly 2 parts for a {n+5}-gon is A055998.

Programs

Mathematica

a[n_] := n*(n + 1)*(n + 7)*(n + 8)/12; Array[a, 40, 0] (* Amiram Eldar, Dec 21 2021 *)

Formula

a(n) = n*(n+1)*(n+7)*(n+8)/12.

G.f.: -x*(12-15*x+5*x^2)/(x-1)^5 . - R. J. Mathar, Aug 03 2022