|
%I #20 May 09 2021 18:30:21
%S 0,1,6,36,228,1518,10530,75516,556512,4194801,32224114,251565996,
%T 1991331720,15953808780,129171585690,1055640440268,8698890336576,
%U 72215877581844,603532770013080,5074488683389840
%N Number of strong triangulations of a fixed square with n interior vertices.
%C A strong triangulation is one in which no interior edge joins two vertices of the square (see W. G. Brown reference).
%C If the restriction "strong" is dropped, the counting sequence is A197271 (shifted left).
%H William G. Brown, <a href="http://dx.doi.org/10.1112/plms/s3-14.4.746">Enumeration of Triangulations of the Disk</a>, Proc. Lond. Math. Soc. s3-14, Issue 4, (1964) 746-768.
%H William T. Tutte, <a href="https://cms.math.ca/cjm/v14/cjm1962v14.0021-0038.pdf">A census of planar triangulations (Eq. 5.12)</a>, Canad. J. Math. 14 (1962), 21-38.
%F 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).
%e 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.
%p A242136:=n->24*binomial(4*n+3,n-1)/((3*n+5)*(n+2)): seq(A242136(n), n=0..30); # _Wesley Ivan Hurt_, Aug 16 2014
%t Table[24 Binomial[4n+3,n-1]/((3n+5)(n+2)), {n, 0, 15}]
%Y Column k=1 of A341856.
%Y Cf. A000260 for triangulations of a triangle.
%K nonn
%O 0,3
%A _David Callan_, Aug 15 2014
|
