login
A253194
Number of ways to place non-intersecting diagonals in a convex (n+2)-gon so as to create no pentagons.
2
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
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
Sequence in context: A371713 A218001 A307490 * A367258 A338185 A151072
KEYWORD
nonn
AUTHOR
Michael D. Weiner, Mar 24 2015
STATUS
approved