A387224 Number of dissections of a convex n-gon by strictly disjoint diagonals so as to create no triangles.

0, 1, 1, 4, 8, 17, 37, 81, 177, 389, 859, 1905, 4241, 9477, 21251, 47806, 107864, 244045, 553575, 1258687, 2868285, 6549757, 14985361, 34347444, 78860152, 181347591, 417653187, 963234195, 2224464087, 5143567237, 11907471643, 27597112946, 64028244032, 148703128913, 345690623119

Offset

3,4

Comments

Strictly disjoint diagonals means that the diagonals are non-crossing and may not share endpoints.

Links

Muhammed Sefa Saydam, Table of n, a(n) for n = 3..104

Formula

a(n) = A004149(n) - A004149(n-2) - 2*A004149(n-3) for n >= 5.

G.f.: (1 - x^2 - 2*x^3)*B(x) - 1 - x + 2*x^3 + 2*x^4, where B(x) is the g.f. of A004149. - Andrew Howroyd, Aug 28 2025

Example

         n=4                         n=5                            n=6
    (1)       (2)                    (1)              (1) (2)     (1) (2)     (1) (2)
                                  (5)   (2)         (6)  \  (3) (6)-----(3) (6)  /  (3)
    (4)       (3)                  (4) (3)            (5) (4)     (5) (4)     (5) (4)
 Diagonal cannot be drawn   Diagonal cannot be drawn
    Number of cases = 1       Number of cases = 1         Number of cases = 3

Prog

(PARI) seq(n) = my(g=2/(1 - x + x^2 + x^3 + sqrt((1-x^4)*(1-2*x-x^2) + O(x*x^n)))); Vec((1 - x^2 - 2*x^3)*g - 1 - x + 2*x^3 + 2*x^4, -n+2) \\ Andrew Howroyd, Aug 28 2025

Crossrefs

Cf. A004149, A093128.

Sequence in context: A215108 A307545 A115618 * A019479 A084814 A098125

Adjacent sequences: A387221 A387222 A387223 * A387225 A387226 A387227

Keyword

nonn

Author

Muhammed Sefa Saydam, Aug 22 2025

Status

approved