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
Keywords
Examples
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.
Links
- D. Birmajer, J. B. Gil, and M. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv:1503.05242 [math.CO], 2015.
Programs
-
Mathematica
Rest[CoefficientList[(InverseSeries[Series[(y-2*y^2+y^4-y^5)/(1-y),{y,0,24}],x]-x)/x,x]] -
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
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