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

Comments

Number of tree interval posets of permutations with n+1 minimal elements. - Mathilde Bouvel, Oct 21 2021

Links

Table of n, a(n) for n=0..26.

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.

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

Example

a(3) = 6 because the pentagon allows null placement and five ways to place two diagonals.

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 *)

Prog

(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

Crossrefs

Cf. A046736, A049124, A003168, A054514, A348479 (free interv. posets not necess. trees).

Sequence in context: A235391 A254316 A279562 * A216490 A150190 A356780

Adjacent sequences: A054512 A054513 A054514 * A054516 A054517 A054518

Keyword

nonn

Author

Len Smiley, Apr 08 2000

Extensions

a(0) = 1 prefixed by R. J. Mathar, Nov 04 2021

Status

approved