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

Links

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

Formula

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

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

Example

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.

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

Prog

(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

Crossrefs

Cf. A001002, A217596.

Sequence in context: A113987 A381539 A188707 * A391170 A360580 A333538

Adjacent sequences: A380588 A380589 A380590 * A380592 A380593 A380594

Keyword

nonn,easy

Author

Muhammed Sefa Saydam, Jan 27 2025

Status

approved