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

Links

Table of n, a(n) for n=9..30.

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.

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

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

Cf. A272982, A350116, A352477.

Sequence in context: A190352 A235175 A235169 * A330413 A251941 A286792

Adjacent sequences: A352471 A352472 A352473 * A352475 A352476 A352477

Keyword

nonn,easy

Author

Janaka Rodrigo, Mar 17 2022

Status

approved