A352474 a(n) is the number of different ways to partition the set of vertices of a convex n-gon into 3 intersecting polygons.

268, 2055, 10285, 42515, 157911, 548912, 1826846, 5902458, 18679974, 58255005, 179762211, 550473301, 1676299353, 5083919214, 15372833564, 46383749572, 139730014800, 420448279875, 1264071072745, 3798101946855, 11406989330923, 34248214094780

Offset: 9

Author

Janaka Rodrigo, Mar 17 2022

Keywords

• nonn
• easy

Examples

			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.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (14,-85,294,-639,906,-839,490,-164,24).

Crossrefs

Cf. A272982, A350116, A352477.

Programs

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

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.

a(n) = A272982(n) - A350116(n-8).

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