OFFSET
9,1
LINKS
Index entries for linear recurrences with constant coefficients, signature (14,-85,294,-639,906,-839,490,-164,24).
FORMULA
a(n) = b(n) - n*(n-1)*(n-7)*(n-8)/12, where b(n) = 3*b(n-1)+C(n-1,2)*(2^(n-4)+2-n-C(n-3,2)) for n > 8 and b(8) = 0. b(n) is given in A272982.
G.f.: x^9*(268 - 1697*x + 4295*x^2 - 5592*x^3 + 4008*x^4 - 1520*x^5 + 240*x^6)/((1 - x)^5*(1 - 2*x)^3*(1 - 3*x)). - Stefano Spezia, Mar 19 2022
EXAMPLE
The set of vertices of a convex 11-gon can be partitioned into 3 polygons in 10395 different ways:
- as 2 triangles and 1 pentagon ((1/2!)*C(11,3)*C(8,3)*C(5,5) = 4620 different ways) or
- as 1 triangle and 2 quadrilaterals ((1/2!)*C(11,3)*C(8,4)*C(4,4) = 5775 different ways).
Subtracting the A350116(11-8) = 110 nonintersecting partitions leaves a(11)=10285.
PROG
(PARI) b(n) = if (n==8, 0, 3*b(n-1)+binomial(n-1, 2)*(2^(n-4)+2-n-binomial(n-3, 2)));
a(n) = b(n) - n*(n-1)*(n-7)*(n-8)/12; \\ Michel Marcus, Mar 19 2022
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Janaka Rodrigo, Mar 17 2022
STATUS
approved