A380591 a(n) is the number of dissections of a convex (n+2)-sided polygon by nonintersecting diagonals into triangles and quadrilaterals such that at least one of the dividing diagonals passes through a chosen vertex.

0, 1, 5, 21, 90, 395, 1773, 8110, 37686, 177450, 844935, 4061762, 19687020, 96107358, 472132330, 2332304055, 11578595554, 57736664825, 289055592810, 1452381167325, 7321620080550, 37020073600755, 187699184460450, 954084756674088, 4861008765722340

Offset: 1

Author

Muhammed Sefa Saydam, Jan 27 2025

Keywords

• nonn
• easy

Examples

			a(2) = 1. Because: Let's choose vertex A in convex quadrilateral ABCD. At least one diagonal must pass through corner A. A diagonal is drawn at corner C. 2 triangles are obtained. There is 1 situation.
a(3) = 5. Because: Let's choose vertex A in convex pentagon ABCDE. At least one diagonal must pass through corner A. First case: diagonals AD and AC can be drawn. Second Case: Diagonals AD and DB can be drawn. Third case: Only diagonal AD can be drawn. Fourth Case: Diagonals AC and EC can be drawn. Fifth Case: Only diagonal AC can be drawn. There are 5 situations in total.
		

Links

• Muhammed Sefa Saydam, Table of n, a(n) for n = 1..100

Crossrefs

Cf. A001002, A217596.

Programs

Maple

a:= proc(n) option remember; `if`(n<3, n*(n-1)/2, (n*(3059*n^2
      -7876*n+4997)*a(n-1)+(4120*n^3-22681*n^2+39305*n-21644)*a(n-2)
      +39*(n-3)*(3*n-10)*(3*n-11)*a(n-3))/(5*(n+1)*n*(142*n-337)))
    end:
seq(a(n), n=1..25);  # Alois P. Heinz, Jan 27 2025

PARI

a(n) = if(n==0,1,if(n==1,-1,-sum(i=ceil(n/2),n,binomial(i,n-i)*binomial(n+i-2,n-2)/(n-1)))) + (1/(n+1))*sum(k=ceil(n/2),n,binomial(n+k,k)*binomial(k,n-k)); \\ Michel Marcus, Jan 27 2025

Formula

a(n) = A001002(n) + A217596(n).

a(n) = -Sum_{i=0..n-2} A217596(i+1) * A001002(n-1-i), n >= 2.