|
|
A242136
|
|
Number of strong triangulations of a fixed square with n interior vertices.
|
|
2
|
|
|
0, 1, 6, 36, 228, 1518, 10530, 75516, 556512, 4194801, 32224114, 251565996, 1991331720, 15953808780, 129171585690, 1055640440268, 8698890336576, 72215877581844, 603532770013080, 5074488683389840
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A strong triangulation is one in which no interior edge joins two vertices of the square (see W. G. Brown reference).
If the restriction "strong" is dropped, the counting sequence is A197271 (shifted left).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 72 * (4*n+3)!/((3*n+6)!*(n-1)!) = 24 * binomial(4*n+3,n-1)/((3*n+5)*(n+2)) = binomial(4*n+3,n-1) - 5 * binomial(4*n+3,n-2) + 6 * binomial(4*n+3,n-3).
|
|
EXAMPLE
|
The 6 triangulations for n=2 are as follows. Four have a central vertex joined to all 4 vertices of the square creating 4 triangular regions, one of which contains the second interior vertex. In these 4 cases, the central vertex has degree 5, the other interior vertex has degree 3. In the other 2 triangulations, both interior vertices have degree 4, an opposite pair a, c of vertices of the square both have degree 3 (so 1 interior edge), and the other 2 opposite vertices have degree 4.
|
|
MAPLE
|
|
|
MATHEMATICA
|
Table[24 Binomial[4n+3, n-1]/((3n+5)(n+2)), {n, 0, 15}]
|
|
CROSSREFS
|
Cf. A000260 for triangulations of a triangle.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|