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
KEYWORD
easy,nonn
AUTHOR
Janaka Rodrigo, Dec 21 2021
STATUS
approved