A054515 -id:A054515 - cp's OEIS frontend

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

Len Smiley, Apr 08 2000

nonn

			a(4)=5 because the octagon has the null placement and four ways to place a single diagonal.

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

Cf. A046736, A049124, A003168, A054515.

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

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

More terms from Joerg Arndt, Jan 28 2014

A348479 Number of interval posets of permutations with n minimal elements.

Original entry on oeis.org

1, 1, 3, 12, 52, 240, 1160, 5795, 29681, 155025, 822563, 4421458, 24025518, 131759106, 728330062, 4053823980, 22699853940, 127790656040, 722835069984, 4106096464006, 23414579166050, 133984343279790, 769124367124594, 4427878983496972, 25559244203741228

Offset: 1

Mathilde Bouvel, Oct 21 2021

nonn

Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Interval Posets and Polygon Dissections, arXiv:2406.16392 [cs.DM], 2024. See p. 2.
Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Geometric view of interval poset permutations, arXiv:2411.13193 [math.CO], 2024. See pp. 2, 6.
Mathilde Bouvel, Lapo Cioni, and Benjamin Izart, The interval posets of permutations seen from the decomposition tree perspective, arXiv:2110.10000 [math.CO], 2021.
Bridget Eileen Tenner, Interval posets for permutations, arXiv:2007.06142 [math.CO], 2020-2021.

For interval posets which are in addition trees, see A054515.

Join[{1},Table[Sum[Sum[Binomial[n+i-1,i]Binomial[i,k]Binomial[n-2k-2,i-1],{k,0,Min[i,(n-i-1)/2]}],{i,n-1}]/n,{n,2,25}]] (* Stefano Spezia, Oct 23 2021 *)

a(n) = if (n==1, 1, (1/n) * sum(i=1, n-1, sum(k=0, min(i,(n-i-1)/2), binomial(n+i-1,i)* binomial(i,k)*binomial(n-2*k-2,i-1)))); \\ Michel Marcus, Oct 21 2021

a(n) = (1/n) * Sum_{i=1..(n-1)} Sum_{k=0..Min(i,(n-i-1)/2)} binomial(n+i-1,i)* binomial(i,k)*binomial(n-2k-2,i-1) if n>1. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 18).
G.f. A(z) = Sum_{n>=0} a(n)*z^n satisfies the equation A(z) = z + (A(z)^2 + A(z)^4)/(1-A(z)). Proved in M. Bouvel, L. Cioni, B. Izart (Equation (1) page 14).
Asymptotic behavior of a(n) is c*n^(-3/2)*r^n with c approximately 0.0622 and r approximately 6.1403. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 19).
D-finite with recurrence 177*n*(n-1)*(n-2) *(1884*n-6797)*a(n) -(n-1) *(n-2) *(2079652*n^2-10492117*n+10802220) *a(n-1) +6*(n-2) *(98404*n^3-611787*n^2+893503*n+124240) *a(n-2) +2*(-1206916*n^4+13262653*n^3-52943063*n^2+90096428*n-54243072) *a(n-3) +(-16564*n^4+1171171*n^3-12487565*n^2+47878166*n-62441016) *a(n-4) +3 *(3*n-14) *(n-5) *(388*n-1861) *(3*n-16)*a(n-5)=0. - R. J. Mathar, Nov 04 2021

A367317 Expansion of (1/x) * Series_Reversion( x * (1-x-x^4/(1-x)) ).

Original entry on oeis.org

1, 1, 2, 5, 15, 50, 177, 649, 2436, 9307, 36080, 141610, 561732, 2248709, 9073415, 36863549, 150676275, 619169360, 2556446520, 10600160707, 44121921044, 184291848864, 772204252280, 3244999395406, 13672564904027, 57749354647408, 244469827514066

Offset: 0

Seiichi Manyama, Jan 26 2024

nonn

Index entries for reversions of series

Cf. A001003, A054515.

Cf. A063021, A367414, A367415.

my(N=30, x='x+O('x^N)); Vec(serreverse(x*(1-x-x^4/(1-x)))/x)

a(n) = sum(k=0, n\4, binomial(n+k, k)*binomial(2*n-2*k, n-4*k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..floor(n/4)} binomial(n+k,k) * binomial(2*n-2*k,n-4*k).

A253194 Number of ways to place non-intersecting diagonals in a convex (n+2)-gon so as to create no pentagons.

Original entry on oeis.org

1, 3, 10, 39, 162, 707, 3190, 14766, 69719, 334481, 1625846, 7989908, 39631204, 198151579, 997623275, 5053274850, 25734158411, 131680565544, 676693557574, 3490897656337, 18071699948492, 93851485181749, 488815126122166

Offset: 1

Michael D. Weiner, Mar 24 2015

nonn

			a(3)=10 because the pentagon allows all but the null placement, i.e., 5 placements of 1 diagonal and 5 placements of two diagonals.

D. Birmajer, J. B. Gil, and M. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv:1503.05242 [math.CO], 2015.

Cf. A046736, A054515.

Rest[CoefficientList[(InverseSeries[Series[(y-2*y^2+y^4-y^5)/(1-y),{y,0,24}],x]-x)/x,x]]

A253194(n)=sum(i=0,(n-1)\3,sum(k=i+1,n-2*i, (-1)^i*binomial(n+k,k)*binomial(k,i)*binomial(n-3*i-1,k-i-1)),if(n%3==0,(-1)^(n/3)*binomial(4*n/3,n/3)))/(n+1) \\ M. F. Hasler, Apr 07 2015

a(n) = (1/(n+1))*Sum_{i=0..floor(n/3)} Sum_{k=i+1..n-2*i} (-1)^i*binomial(n+k,k)*binomial(k,i)*binomial(n-3*i-1,k-i-1), n !== 0 (mod 3),
a(n) = ((-1)^(n/3)/(n+1))*binomial(4*n/3,n/3) + (1/(n+1))*Sum_{i=0..(n/3)-1} Sum_{k=i+1..n-2*i} (-1)^i*binomial(n+k,k)*binomial(k,i)*binomial(n-3*i-1,k-i-1), n == 0 (mod 3).
Recurrence: 275*(n-2)*(n-1)*n*(n+1)*(13962464*n^5 - 196202616*n^4 + 1069508732*n^3 - 2802358002*n^2 + 3480787751*n - 1597000860)*a(n) = 900*(n-2)*(n-1)*n*(27924928*n^6 - 406367696*n^5 + 2336399896*n^4 - 6678345644*n^3 + 9735406192*n^2 - 6526643891*n + 1424056473)*a(n-1) - 8*(n-2)*(n-1)*(1870970176*n^7 - 30033090896*n^6 + 197840216728*n^5 - 682911269612*n^4 + 1297104157966*n^3 - 1273486799084*n^2 + 486871358313*n + 21712608900)*a(n-2) - 16*(n-2)*(2569093376*n^8 - 47662201536*n^7 + 375012676176*n^6 - 1627682459628*n^5 + 4239503473896*n^4 - 6734585440155*n^3 + 6299789310412*n^2 - 3112752665481*n + 598681926090)*a(n-3) + 16*(2457393664*n^9 - 54190809728*n^8 + 518749193184*n^7 - 2816319789288*n^6 + 9492888047100*n^5 - 20388222826734*n^4 + 27407291375141*n^3 - 21462176121217*n^2 + 8117426803296*n - 745665750648)*a(n-4) - 8*(n-4)*(2*n - 7)*(4*n - 17)*(4*n - 11)*(13962464*n^5 - 126390296*n^4 + 424322908*n^3 - 631422862*n^2 + 369599799*n - 31302531)*a(n-5). - Vaclav Kotesovec, Mar 30 2015

A367413 Expansion of (1/x) * Series_Reversion( x * (1-x-x^3/(1-x)^2) ).

Original entry on oeis.org

1, 1, 2, 6, 22, 87, 356, 1493, 6398, 27936, 123906, 556734, 2528668, 11590555, 53545932, 249065874, 1165482126, 5482782933, 25914899804, 123009541412, 586121731150, 2802470267460, 13441993044464, 64660400422341, 311861855749484, 1507802756171072, 7306422899878394

Offset: 0

Seiichi Manyama, Jan 26 2024

nonn

Index entries for reversions of series

Cf. A378464.
Cf. A049140, A054515.
Cf. A378466, A378467.

my(N=30, x='x+O('x^N)); Vec(serreverse(x*(1-x-x^3/(1-x)^2))/x)

a(n) = sum(k=0, n\3, binomial(n+k, k)*binomial(2*n, n-3*k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..floor(n/3)} binomial(n+k,k) * binomial(2*n,n-3*k).
From Seiichi Manyama, Nov 27 2024: (Start)
G.f.: exp( Sum_{k>=1} A378464(k) * x^k/k ).
a(n) = (1/(n+1)) * [x^n] 1/(1 - x - x^3/(1 - x)^2)^(n+1). (End)

A373456 Number of tree interval posets of permutations of size n, considered up to isomorphism.

Original entry on oeis.org

1, 1, 1, 3, 6, 14, 32, 79, 192, 488, 1244, 3240, 8497, 22561, 60309, 162541, 440598, 1201377, 3291426, 9058464, 25027797, 69401101, 193071153, 538724060, 1507288378, 4227824974, 11886150870, 33488522111, 94539554742, 267383598840, 757539956852, 2149698586706, 6109515731611

Offset: 1

Mathilde Bouvel, Jun 06 2024

nonn

See Remark 24 in [Bouvel-Cioni-Izart].

Bridget E. Tenner. Interval Posets of Permutations. Order, 39(3):523-536, 2022.

Mathilde Bouvel, Lapo Cioni, and Benjamin Izart, The interval posets of permutations seen from the decomposition tree perspective, arXiv:2110.10000 [math.CO], 2021-2024.
Bridget E. Tenner, Interval Posets for Permutations, arXiv:2007.06142 [math.CO], 2020-2021.

For the same posets but not considered up to isomorphism, see A054515.

For interval posets that are not necessarily trees, see A373455 (for posets also considered up to isomorphism) and A348479 (otherwise).

Asymptotic behavior of a(n) is c*n^(-3/2)*r^n with c approximately 0.2597 and r approximately 2.9784. See M. Bouvel, L. Cioni, B. Izart (Remark 24).

A378463 a(n) = Sum_{k=0..floor(n/3)} binomial(n+k-1,k) * binomial(2n-k-1,n-3k).

Original entry on oeis.org

1, 1, 3, 13, 59, 266, 1203, 5489, 25259, 117022, 545038, 2549592, 11970035, 56372460, 266194295, 1259910113, 5975382699, 28390616727, 135108035502, 643891031826, 3072604703774, 14679493913048, 70206875750168, 336103001918788, 1610476039036259, 7723148579525441

Offset: 0

Seiichi Manyama, Nov 27 2024

nonn

Cf. A370624, A378464.

Cf. A054515.

a(n) = sum(k=0, n\3, binomial(n+k-1, k)*binomial(2*n-k-1, n-3*k));

a(n) = [x^n] 1/(1 - x - x^3/(1 - x))^n.

A256752 Number of ways to place non-intersecting diagonals in a convex (n+2)-gon so as to create no hexagons.

Original entry on oeis.org

1, 3, 11, 44, 190, 859, 4015, 19248, 94117, 467575, 2353443, 11975568, 61505088, 318406927, 1659801852, 8704865907, 45898065978, 243163198928, 1293769867676, 6910165762943, 37036898772008, 199140325574519, 1073849938338566

Offset: 1

Michael D. Weiner, Apr 09 2015

nonn

			a(3)=11 because all 11 dissections of the pentagon are allowed, i.e., the null placement, 5 placements of 1 diagonal and 5 placements of two diagonals.

D. Birmajer, J. B. Gil, and M. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv:1503.05242 [math.CO], 2015.

Cf. A046736, A054515, A253194.

Rest[CoefficientList[(InverseSeries[Series[(y-2*y^2+y^5-y^6)/(1-y), {y, 0, 24}], x]-x)/x, x]]

a(n) = (1/(n+1))*Sum_{i=0..floor(n/4)} Sum_{k=i+1..n-3*i} (-1)^i*binomial(n+k,k)*binomial(k,i)*binomial(n-4*i-1,k-i-1), n !== 0 (mod 4),

a(n) = ((-1)^(n/4)/(n+1))*binomial(5*n/4,n/4) + (1/(n+1))*Sum_{i=0..(n/4)-1} Sum_{k=i+1..n-3*i} (-1)^i*binomial(n+k,k)*binomial(k,i)*binomial(n-4*i-1,k-i-1), n == 0 (mod 4).

cp's OEIS Frontend

A054514 Number of ways to place non-crossing diagonals in convex (n+4)-gon so as to create no triangles or quadrilaterals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A348479 Number of interval posets of permutations with n minimal elements.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A367317 Expansion of (1/x) * Series_Reversion( x * (1-x-x^4/(1-x)) ).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A253194 Number of ways to place non-intersecting diagonals in a convex (n+2)-gon so as to create no pentagons.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A367413 Expansion of (1/x) * Series_Reversion( x * (1-x-x^3/(1-x)^2) ).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A373456 Number of tree interval posets of permutations of size n, considered up to isomorphism.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A378463 a(n) = Sum_{k=0..floor(n/3)} binomial(n+k-1,k) * binomial(2*n-k-1,n-3*k).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A256752 Number of ways to place non-intersecting diagonals in a convex (n+2)-gon so as to create no hexagons.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A378463 a(n) = Sum_{k=0..floor(n/3)} binomial(n+k-1,k) * binomial(2n-k-1,n-3k).