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

0, 0, 0, 7, 28, 79, 460, 2486, 11209, 59787, 361777, 2167635, 13577211, 91919186, 650059294, 4761980740, 36508824672, 292116858616, 2424047807182, 20847409357919, 185754041370693, 1711253802075941, 16272637412753211, 159561718074359537, 1611599794862761838, 16747401536440092104

Offset

3,4

Links

Table of n, a(n) for n=3..28.

Formula

a(n) = A006505(n) - A114997(n).

a(n) = Sum_{k=2..floor(n/3)} (T(n,k) - C(n+1,k)*C(n-2k-1,k-1)/(n+1)); n > 5, where T(n,k) = k*T(n-1,k) + C(n-1,2)*T(n-3,k-1); n > 5 and 1 < k <= floor(n/3), T(n,k) = 1 when k = 1.

T(n,k) = A059022(n,k) is the number of different ways to partition the set of vertices of a convex n-gon into k polygons.

Example

For n=6, there are a(6) = 7 intersecting partitions of the convex hexagon. On vertices 1..6, they are the following pairs of triangles:
  {1,3,4}{5,6,2}
  {4,5,1}{2,3,6}
  {3,4,6}{1,2,5}
  {2,3,5}{1,4,6}
  {1,2,4}{5,6,3}
  {1,6,3}{5,4,2}
  {1,3,5}{2,4,6}

Prog

(PARI) T2(n, k) = if (n<3, 0, if (k==1, 1, k*T2(n-1, k) + binomial(n-1, 2)*T2(n-3, k-1))); \\ A059022
a5(n) = if (n<3, n==0, sum(k=1, n\3, T2(n, k))); \\ A006505
a7(n) = sum(k=ceil((n+3)/2), n, (1/(n+1) * binomial(n+1, k) * binomial(2*k-n-3, n-k)) ); \\ A114997
a(n) =  a5(n) - a7(n); \\ Michel Marcus, Apr 09 2022

Crossrefs

Cf. A006505, A114997, A059022, A350248.

Sequence in context: A061968 A223772 A024012 * A163705 A162595 A073363

Adjacent sequences: A352897 A352898 A352899 * A352901 A352902 A352903

Keyword

nonn,more

Author

Janaka Rodrigo, Apr 07 2022

Extensions

More terms from Michel Marcus, Apr 09 2022

Status

approved