A341856 Array read by antidiagonals: T(n,k) is the number of rooted strong triangulations of a disk with n interior nodes and 3+k nodes on the boundary.

1, 0, 1, 0, 1, 3, 0, 1, 6, 13, 0, 1, 10, 36, 68, 0, 1, 15, 80, 228, 399, 0, 1, 21, 155, 610, 1518, 2530, 0, 1, 28, 273, 1410, 4625, 10530, 16965, 0, 1, 36, 448, 2933, 12165, 35322, 75516, 118668, 0, 1, 45, 696, 5628, 28707, 102548, 272800, 556512, 857956

Offset

0,6

Comments

A strong triangulation is one in which no interior edge joins two nodes on the boundary. Except for the single triangle which is enumerated by T(0,0) these are the 3-connected triangulations.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325

William T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962), 21-38.

Formula

T(n,0) = A000260(n) = 2*(4*n+1)!/((3*n+2)!*(n+1)!).

T(n,m) = (3*(m+2)!*(m-1)!/(3*n+3*m+3)!) * Sum_{j=0..min(m,n-1)} (4*n+3*m-j+1)!*(m+j+2)*(m-3*j)/(j!*(j+1)!*(m-j)!*(m-j+2)!*(n-j-1)!) for m > 0.

Example

Array begins:
=======================================================
n\k |    0     1     2      3      4      5       6
----+--------------------------------------------------
  0 |    1     0     0      0      0      0       0 ...
  1 |    1     1     1      1      1      1       1 ...
  2 |    3     6    10     15     21     28      36 ...
  3 |   13    36    80    155    273    448     696 ...
  4 |   68   228   610   1410   2933   5628   10128 ...
  5 |  399  1518  4625  12165  28707  62230  125928 ...
  6 | 2530 10530 35322 102548 267162 638624 1422204 ...
  ...

Prog

(PARI) T(n, m)=if(m==0, 2*(4*n+1)!/((3*n+2)!*(n+1)!), (3*(m+2)!*(m-1)!/(3*n+3*m+3)!)*sum(j=0, min(m, n-1), (4*n+3*m-j+1)!*(m+j+2)*(m-3*j)/(j!*(j+1)!*(m-j)!*(m-j+2)!*(n-j-1)!)))

Crossrefs

Columns k=0..3 are A000260, A242136, A341917, A341918.

Antidiagonal sums give A341919.

Cf. A146305 (not necessarily strong triangulations), A210664, A341923, A342053.

Sequence in context: A243984 A100485 A143397 * A339350 A244118 A273155

Adjacent sequences: A341853 A341854 A341855 * A341857 A341858 A341859

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 23 2021

Status

approved