A054514 Number of ways to place non-crossing diagonals in convex (n+4)-gon so as to create no triangles or quadrilaterals.
1, 1, 1, 5, 10, 16, 45, 109, 222, 540, 1341, 3065, 7328, 18112, 43530, 105390, 260254, 639244, 1570257, 3893805, 9669236, 24014264, 59903650, 149806494, 374982790, 940835404, 2365679689, 5955973237, 15018854005, 37935575685, 95942896837, 242954350457, 616034170069, 1563810857705, 3974000543475
Offset: 1
Keywords
Examples
a(4)=5 because the octagon has the null placement and four ways to place a single diagonal.
Links
- Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Blockwise simple permutations, arXiv:2303.13115 [math.CO], 2023.
- Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Geometric view of interval poset permutations, arXiv:2411.13193 [math.CO], 2024. See p. 10.
- D. Birmajer, J. B. Gil, M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
- Len Smiley, Generalization and some variants
Programs
-
Mathematica
f[x_] = InverseSeries[Series[(y - y^2 - y^4)/(1 - y), {y, 0, 38}], x]; CoefficientList[(f[x] - x)/x^4, x] (* Second program: *) a[n_] := Sum[Binomial[n-2j-1, n-3j-1] Binomial[n+3+j, n+2]/(n+3), {j, 0, (n-1)/3}]; Array[a, 35] (* Jean-François Alcover, Dec 08 2018, after David Callan *) Table[HypergeometricPFQ[{1/3 - n/3, 2/3 - n/3, 1 - n/3, 4 + n}, {2, 1/2 - n/2, 1 - n/2}, -27/4], {n, 1, 40}] (* Vaclav Kotesovec, Sep 16 2023 *)
Formula
a(n) = Sum_{j=0..(n-1)/3} binomial[n-2j-1, n-3j-1] binomial[n+3+j, n+2]/(n+3). This counts the polygon dissections above by number j of diagonals. - David Callan, Jul 15 2004
Extensions
More terms from Joerg Arndt, Jan 28 2014