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,2

Comments

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

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

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

Example

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.

Mathematica

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

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.

Sequence in context: A135710 A358465 A070996 * A015237 A024223 A251720

Adjacent sequences: A350113 A350114 A350115 * A350117 A350118 A350119

Keyword

easy,nonn

Author

Janaka Rodrigo, Dec 21 2021

Status

approved