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,5

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

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

Formula

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

Example

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 ...
  ...

Prog

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

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).

Sequence in context: A279436 A082470 A101204 * A328395 A283069 A304528

Adjacent sequences: A169805 A169806 A169807 * A169809 A169810 A169811

Keyword

nonn,tabl

Author

N. J. A. Sloane, May 25 2010

Extensions

Edited by Andrew Howroyd, Feb 22 2021

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

Status

approved