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

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

Links

Table of n, a(n) for n=1..23.

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

Formula

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

Example

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.

Mathematica

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

Prog

(PARI) 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

Crossrefs

Cf. A046736, A054515.

Sequence in context: A371713 A218001 A307490 * A367258 A338185 A151072

Adjacent sequences: A253191 A253192 A253193 * A253195 A253196 A253197

Keyword

nonn

Author

Michael D. Weiner, Mar 24 2015

Status

approved