|
Search: id:A046736
|
|
|
| A046736 |
|
Number of ways to place non-intersecting diagonals in convex n-gon so as to create no triangles. |
|
+0
5
|
|
| 1, 0, 1, 1, 4, 8, 25, 64, 191, 540, 1616, 4785, 14512, 44084, 135545, 418609, 1302340, 4070124, 12785859, 40325828, 127689288, 405689020, 1293060464, 4133173256, 13246527139, 42557271268, 137032656700, 442158893833, 1429468244788
(list; graph; listen)
|
|
|
OFFSET
|
2,5
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=2..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 93
L. Smiley, A Nameless Number
L. Smiley, [math/9907057] Variants of Schroeder Dissections
|
|
FORMULA
|
G.f.: A(x)=sum_{n>0} a(n)x^(n-1) satisfies A(x)-A(x)^2-A(x)^3 = x*(1-A(x)).
Let g=(1-x)/(1-x-x^2); then a(m) = coeff. of x^(m-2) in g^(m-1)/(m-1).
|
|
EXAMPLE
|
a(4)=a(5)=1 because of null placement; a(6)=4 because in addition to not placing any, we might also place one between any of the 3 pairs of opposite vertices.
|
|
MAPLE
|
a := n->1/(n-1)*sum(binomial(n+k-2, k)*binomial(n-k-3, k-1), k=0..floor(n/2-1)); seq(a(i), i=2..30);
|
|
MATHEMATICA
|
a[2]=1; a[n_] := Sum[Binomial[n+k-2, k]*Binomial[n-k-3, k-1], {k, 0, Floor[n/2]-1}]/(n-1);
x*InverseSeries[Series[(y-y^2-y^3)/(1-y), {y, 0, 29}], x]
|
|
PROGRAM
|
(PARI) a(n)=if(n<2, 0, polcoeff(serreverse((x-x^2-x^3)/(1-x)+x*O(x^n)), n-1))
|
|
CROSSREFS
|
Cf. A000108 (Catalan), A001003 (Schroeder), A001006 (Motzkin).
A052524(n)=n!*a(n+1) for n>0.
Adjacent sequences: A046733 A046734 A046735 this_sequence A046737 A046738 A046739
Sequence in context: A068367 A000964 A107840 this_sequence A074188 A126733 A012982
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
Len Smiley (smiley(AT)math.uaa.alaska.edu)
|
|
EXTENSIONS
|
More terms from James A. Sellers (sellersj(AT)math.psu.edu), Feb 16 2000
|
|
|
Search completed in 0.002 seconds
|
