A054515 Number of ways to place non-intersecting diagonals in convex (n+2)-gon so as to create no quadrilaterals.
1, 1, 2, 6, 21, 78, 301, 1198, 4888, 20340, 85986, 368239, 1594183, 6965380, 30675399, 136026759, 606848034, 2721783023, 12265670909, 55511013680, 252193872912, 1149742659556, 5258257323304, 24117924005616, 110915268468358, 511334146237807, 2362650323603539
Offset: 0
Keywords
Examples
a(3) = 6 because the pentagon allows null placement and five ways to place two diagonals.
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 pp. 3, 8.
- Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015
- Mathilde Bouvel, Lapo Cioni, and Benjamin Izart, The interval posets of permutations seen from the decomposition tree perspective, arXiv:2110.10000 [math.CO], 2021.
- Len Smiley, Generalization and some variants, see Quad-free.
- Bridget Eileen Tenner, Interval posets for permutations, arXiv:2007.06142 [math.CO], 2020-2021.
Programs
-
Maple
read("transforms") : taylor( (1-2*y+y^2-y^3)/(1-y),y=0,50) ; gfun[seriestolist](%) ; REVERT(%) ; # R. J. Mathar, Nov 04 2021 -
Mathematica
InverseSeries[Series[(y-2*y^2+y^3-y^4)/(1-y), {y, 0, 24}], x] (* then A(x)=[y(x)-x]/x *) -
PARI
my(N=28, x='x+O('x^N)); Vec(serreverse((x-2*x^2+x^3-x^4)/(1-x))) \\ Hugo Pfoertner, Jan 26 2024
Formula
REVERT transform of (1-2*x+x^2-x^3)/(1-x) [Smiley].
a(n-1) = (1/n) * [binomial(2n-2,n-1) + Sum_{i=1..(n-3)} Sum_{k=1..Min(i,(n-i-1)/2)} binomial(n+i-1,i)*binomial(i,k)*binomial(n-i-k-2,k-1) ] if n>1. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 21) with offset 1. - Mathilde Bouvel, Oct 21 2021
G.f. A(z) = Sum_{n>=0} a(n)*z^n satisfies A(z) = 1 + z*A^2 + z^3*A^4/(1-z*A). Proved in M. Bouvel, L. Cioni, B. Izart (Equation (6) page 17 with offset 1). - Mathilde Bouvel, Oct 21 2021
Asymptotic behavior of a(n-1) is c*n^(-3/2)*r^n with c approximately 0.0792 and r approximately 4.8920. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 22). - Mathilde Bouvel, Oct 21 2021
D-finite with recurrence 23 *n *(n-1) *(12869043*n-33144451) *(n+1) *a(n) -n *(n-1) *(1989552043*n^2-6117767430*n+2643232213) * a(n-1) +(n-1) *(3359030609*n^3-15361701516*n^2+20123332181*n-6949961920) *a(n-2) +(-3560897749*n^4+25182507306*n^3-62054513365*n^2 +60006265908*n-16495478980) *a(n-3) +3*(146027817*n^4-1247820696*n^3+3378236999*n^2-2363753280*n-1468123920)*a(n-4) -3*(335627*n+695280) *(3*n-13) *(3*n-11) *(n-4) *a(n-5)=0. - R. J. Mathar, Oct 28 2021
a(n) = (1/(n+1)) * Sum_{k=0..floor(n/3)} binomial(n+k,k) * binomial(2*n-k,n-3*k). - Seiichi Manyama, Jan 26 2024
Extensions
a(0) = 1 prefixed by R. J. Mathar, Nov 04 2021
Comments