A169808 Array T(n,k) read by antidiagonals: T(n,k) is the number of [n,k]-triangulations in the plane, n >= 0, k >= 0.

1, 1, 1, 1, 2, 1, 3, 4, 5, 4, 4, 11, 14, 18, 16, 12, 28, 53, 69, 88, 78, 27, 91, 178, 295, 396, 489, 457, 82, 291, 685, 1196, 1867, 2503, 3071, 2938, 228, 1004, 2548, 5051, 8385, 12560, 16905, 20667, 20118, 733, 3471, 9876, 21018, 38078, 60736, 89038, 119571, 146381, 144113

Offset: 0

Author

N. J. A. Sloane, May 25 2010

Keywords

• nonn
• tabl

Comments

"A closed bounded region in the plane divided into triangular regions with k+3 vertices on the boundary and n internal vertices is said to be a triangular map of type [n,k]." It is a [n,k]-triangulation if there are no multiple edges.

T(n,k) is the number of floor plan arrangements represented by 3-connected trivalent maps with n internal rooms and k+3 rooms adjacent to the outside.

"... may be evaluated from the results given by Brown."

The initial terms of this sequence can also be computed using the tool "plantri", in particular the command "./plantri -u -v -P -c2m2 [n]" will compute values for a diagonal. The '-c2' and '-m2' options indicate graphs must be biconnected and with minimum vertex degree 2. - Andrew Howroyd, Feb 22 2021

Examples

			Array begins:
============================================================
n\k |    0     1      2      3       4        5        6
----+-------------------------------------------------------
  0 |    1     1      1      3       4       12       27 ...
  1 |    1     2      4     11      28       91      291 ...
  2 |    1     5     14     53     178      685     2548 ...
  3 |    4    18     69    295    1196     5051    21018 ...
  4 |   16    88    396   1867    8385    38078   169918 ...
  5 |   78   489   2503  12560   60736   290595  1367374 ...
  6 |  457  3071  16905  89038  451613  2251035 11025626 ...
  7 | 2938 20667 119571 652198 3429943 17658448 89328186 ...
  ...
		

References

• C. F. Earl and L. J. March, Architectural applications of graph theory, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1325
• G. Brinkmann and B. McKay, Plantri (program for generation of certain types of planar graph)
• William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.
• William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768. [Annotated scanned copy].
• C. F. Earl and L. J. March, Architectural applications of graph theory, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979. (Annotated scanned copy)
• Andrew Howroyd, PARI Program

Crossrefs

Columns k=0..3 are A002713, A005500, A005501, A005502.

Rows n=0..2 are A000207, A005503, A005504.

Antidiagonal sums give A005027.

Cf. A146305 (rooted), A169809 (achiral), A262586 (oriented).

Programs

PARI

\\ See link for script file.
A169808Array(6) \\ Andrew Howroyd, Feb 22 2021

Formula

T(n,k) = (A262586(n,k) + A169809(n,k)) / 2. - Andrew Howroyd, Feb 22 2021

Extensions

Edited by Andrew Howroyd, Feb 22 2021

a(29) corrected and terms a(36) and beyond from Andrew Howroyd, Feb 22 2021