%I #31 Apr 03 2022 08:57:11
%S 268,2055,10285,42515,157911,548912,1826846,5902458,18679974,58255005,
%T 179762211,550473301,1676299353,5083919214,15372833564,46383749572,
%U 139730014800,420448279875,1264071072745,3798101946855,11406989330923,34248214094780
%N a(n) is the number of different ways to partition the set of vertices of a convex n-gon into 3 intersecting polygons.
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (14,-85,294,-639,906,-839,490,-164,24).
%F 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.
%F a(n) = A272982(n) - A350116(n-8).
%F 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
%e The set of vertices of a convex 11-gon can be partitioned into 3 polygons in 10395 different ways:
%e - as 2 triangles and 1 pentagon ((1/2!)*C(11,3)*C(8,3)*C(5,5) = 4620 different ways) or
%e - as 1 triangle and 2 quadrilaterals ((1/2!)*C(11,3)*C(8,4)*C(4,4) = 5775 different ways).
%e Subtracting the A350116(11-8) = 110 nonintersecting partitions leaves a(11)=10285.
%o (PARI) b(n) = if (n==8, 0, 3*b(n-1)+binomial(n-1,2)*(2^(n-4)+2-n-binomial(n-3,2)));
%o a(n) = b(n) - n*(n-1)*(n-7)*(n-8)/12; \\ _Michel Marcus_, Mar 19 2022
%Y Cf. A272982, A350116, A352477.
%K nonn,easy
%O 9,1
%A _Janaka Rodrigo_, Mar 17 2022
|