login
A352474
a(n) is the number of different ways to partition the set of vertices of a convex n-gon into 3 intersecting polygons.
0
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
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
KEYWORD
nonn,easy
AUTHOR
Janaka Rodrigo, Mar 17 2022
STATUS
approved