A169809 -id:A169809 - cp's OEIS frontend

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

N. J. A. Sloane, May 25 2010

"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

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

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.

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

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

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

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

Edited by Andrew Howroyd, Feb 22 2021

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

A262586 Square array T(n,m) (n>=0, m>=0) read by antidiagonals downwards giving number of rooted triangulations of type [n,m] up to orientation-preserving isomorphisms.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 4, 5, 6, 5, 6, 16, 21, 26, 24, 19, 48, 88, 119, 147, 133, 49, 164, 330, 538, 735, 892, 846, 150, 559, 1302, 2310, 3568, 4830, 5876, 5661, 442, 1952, 5005, 9882, 16500, 24596, 33253, 40490, 39556, 1424, 6872, 19504, 41715, 75387, 120582, 176354, 237336, 290020, 286000, 4522

Offset: 0

N. J. A. Sloane, Oct 20 2015

			Array begins:
 ==============================================================
 n\k |    0     1      2       3       4        5         6 ...
 ----+---------------------------------------------------------
   0 |    1     1      1       4       6       19        49 ...
   1 |    1     2      5      16      48      164       559 ...
   2 |    1     6     21      88     330     1302      5005 ...
   3 |    5    26    119     538    2310     9882     41715 ...
   4 |   24   147    735    3568   16500    75387    338685 ...
   5 |  133   892   4830   24596  120582   578622   2730728 ...
   6 |  846  5876  33253  176354  900240  4493168  22037055 ...
   7 | 5661 40490 237336 1298732 6849810 35286534 178606610 ...
   ...
The first few antidiagonals are:
  1,
  1,1,
  1,2,1,
  4,5,6,5,
  6,16,21,26,24,
  19,48,88,119,147,133,
  49,164,330,538,735,892,846,
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals).
Jean-François Alcover, Mathematica code
W. G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768. [Annotated scanned copy]. See Table 1 (with a typo at G(n=1,m=6)).
L. March and C. F. Earl, On Counting Architectural Plans, Environment and Planning B, 4 (1977), 57-80. See Table 2.

Columns 0..2 are A002709, A002710, A002711.
Rows 0..3 are A001683, A210696, A005498, A005499.
Antidiagonal sums are A341855.
Cf. A169808 (unoriented), A169809 (achiral).

A262586 := proc(n,m)
    BrownG(n,m) ; # procedure in A210696
end proc:
for d from 0 to 12 do
    for n from 0 to d do
        printf("%d,",A262586(n,d-n)) ;
    end do:
end do: # R. J. Mathar, Oct 21 2015

Mathematica
```
(* See LINKS section. *)
```

\\ See Links in A169808 for PARI program file.
{ for(n=0, 7, for(k=0, 7, print1(OrientedTriangs(n,k), ", ")); print) } \\ Andrew Howroyd, Nov 23 2024

Brown (Eq. 6.3) gives a formula.

A146305 Array T(n,m) = 2(2m+3)!(4n+2m+1)!/(m!(m+2)!n!*(3n+2m+3)!) read by antidiagonals.

Original entry on oeis.org

1, 1, 2, 3, 5, 5, 13, 20, 21, 14, 68, 100, 105, 84, 42, 399, 570, 595, 504, 330, 132, 2530, 3542, 3675, 3192, 2310, 1287, 429, 16965, 23400, 24150, 21252, 16170, 10296, 5005, 1430, 118668, 161820, 166257, 147420, 115500, 78936, 45045, 19448, 4862, 857956

Offset: 0

R. J. Mathar, Oct 29 2008

T(n,m) is the number of rooted nonseparable (2-connected) triangulations of the disk with n internal nodes and 3 + m nodes on the external face. The triangulation has 2*n + m + 1 triangles and 3*(n+1) + 2*m edges. - Andrew Howroyd, Feb 21 2021

			The array starts at row n=0 and column m=0 as
.....1......2.......5......14.......42.......132
.....1......5......21......84......330......1287
.....3.....20.....105.....504.....2310.....10296
....13....100.....595....3192....16170.....78936
....68....570....3675...21252...115500....602316
...399...3542...24150..147420...844074...4628052
..2530..23400..166257.1057224..6301680..35939904
.16965.161820.1186680.7791168.47948670.282285432

Andrew Howroyd, Table of n, a(n) for n = 0..1325
Alin Bostan, Frédéric Chyzak, and Vincent Pilaud, Refined product formulas for Tamari intervals, arXiv:2303.10986 [math.CO], 2023.
William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.

Columns m=0..3 are A000260, A197271(n+1), A341853, A341854.
Rows n=0..2 are A000108(n+1), A002054(n+1) and A000917.
Antidiagonal sums are A000260(n+1).
Cf. A169808 (unrooted), A169809 (achiral), A262586 (oriented).

A146305 := proc(n,m)
    2*(2*m+3)!*(4*n+2*m+1)!/m!/(m+2)!/n!/(3*n+2*m+3)! ;
end proc:
for d from 0 to 13 do
    for m from 0 to d do
        printf("%d,", A146305(d-m,m)) ;
    end do:
end do:

T[n_, m_] := 2*(2*m+3)!*(4*n+2*m+1)!/m!/(m+2)!/n!/(3*n+2*m+3)!; Table[T[n-m, m], {n, 0, 13}, {m, 0, n}] // Flatten (* Jean-François Alcover, Jan 06 2014, after Maple *)

T(n,m)={2*(2*m+3)!*(4*n+2*m+1)!/(m!*(m+2)!*n!*(3*n+2*m+3)!)} \\ Andrew Howroyd, Feb 21 2021

A005028 Number of symmetric trivalent maps with n nodes.

Original entry on oeis.org

1, 2, 4, 12, 33, 102, 312, 1010, 3256, 10836, 36094, 122544, 417150, 1437712, 4970904, 17333772, 60638124, 213435264, 753520804, 2672606464, 9505230397, 33928264990, 121400935184, 435660446342, 1566809204928, 5648450745204, 20402191885146, 73842311224632

Offset: 3

N. J. A. Sloane

nonn

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 3..500
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)

Antidiagonal sums of the array in A169809.

Cf. A005027.

Terms a(11) and beyond from Andrew Howroyd, Feb 22 2021

A002712 Number of unrooted triangulations of a disk that have reflection symmetry with n interior nodes and 3 nodes on the boundary.

Original entry on oeis.org

1, 1, 1, 3, 8, 23, 68, 215, 680, 2226, 7327, 24607, 83060, 284046, 975950, 3383343, 11778308, 41269252, 145131502, 512881550, 1818259952, 6470758289, 23091680690, 82659905947, 296605398856, 1067012168350, 3846553544904, 13896522968160, 50296815014780, 182378110257354, 662384549806938

Offset: 0

N. J. A. Sloane

nonn

These are also called [n,0]-triangulations.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..500
William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.
W. 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)

Column k=0 of A169809.

Dc := proc(n,m) 2*(2*m+3)!*(4*n+2*m+1)!/m!/(m+2)!/n!/(3*n+2*m+3)! ; end:
A000260 := proc(n) Dc(n,0) ; end:
Dx2 := proc(nmax) add( A000260(n)*x^(2*n),n=0..nmax) ; end:
o := 20: Order := 2*o-1 : j := solve( J0=1+x*J0+x^2*J0*(1+x*J0/2)*series(J0^2-Dx2(o),x=0,2*o-1),J0) ;
for n from 0 to 2*o-2 do printf("%d,",coeftayl(j,x=0,n)) ; od: # R. J. Mathar, Oct 29 2008

seq[m_] := Module[{q}, q = Sum[x^(2n) Binomial[4n+2, n+1]/ ((2n+1)(3n+2)), {n, 0, Quotient[m, 2]}]; p = 1+O[x]; Do[p = 1 + x*p + x^2*p*(1+x*p/2)(p^2-q), {n, 1, m}]; CoefficientList[p, x]];
seq[30] (* Jean-François Alcover, Apr 25 2023, after Andrew Howroyd *)

seq(n)={my(q=sum(n=0, n\2, x^(2*n)*binomial(4*n+2, n+1)/((2*n+1)*(3*n+2))), p=1+O(x)); for(n=1, n, p = 1 + x*p + x^2*p*(1 + x*p/2)*(p^2 - q)); Vec(p)} \\ Andrew Howroyd, Feb 24 2021

More terms from R. J. Mathar, Oct 29 2008

Name clarified and terms a(27) and beyond from Andrew Howroyd, Feb 24 2021

A005505 Number of unrooted triangulations with reflection symmetry of a quadrilateral with n internal nodes.

Original entry on oeis.org

1, 2, 4, 10, 29, 86, 266, 844, 2742, 9032, 30202, 101988, 347914, 1195500, 4138310, 14405848, 50428392, 177321636, 626250990, 2219876580, 7896651847, 28176271634, 100830069380, 361757157484, 1301092926454, 4689840961196, 16940093338162, 61305930699382

Offset: 0

N. J. A. Sloane

nonn

These are also called [n,1]-triangulations.

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..500
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)
C. F. Earl & N. J. A. Sloane, Correspondence, 1980-1981

Column k=1 of the array in A169809.

Cf. A002710, A005500.

a(n) = 2 * A005500(n) - A002710(n) (based on Max Alekseyev's formula, cf. A005500).

a(7)-a(12) from Altug Alkan and Manfred Scheucher, Mar 08 2018

Name clarified and terms a(13) and beyond from Andrew Howroyd, Feb 21 2021

A005506 Number of unrooted triangulations with reflection symmetry of a pentagon with n internal nodes.

Original entry on oeis.org

1, 3, 7, 19, 57, 176, 557, 1806, 5954, 19897, 67235, 229366, 788688, 2730810, 9512107, 33309444, 117190184, 414039578, 1468349782, 5225201321, 18651958885, 66769742002, 239643164237, 862168692562, 3108716586702, 11232127258416, 40660388117380, 147453014455094

Offset: 0

N. J. A. Sloane

nonn

These are also called [n,2]-triangulations.

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..200
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)
C. F. Earl & N. J. A. Sloane, Correspondence, 1980-1981

Column k=2 of the array in A169809.

Cf. A002711, A005501.

a(n) = 2 * A005501(n) - A002711(n) (based on Max Alekseyev's formula, cf. A005501).

a(6)-a(11) from Altug Alkan and Manfred Scheucher, Mar 08 2018

Name clarified and terms a(12) and beyond from Andrew Howroyd, Feb 21 2021

A005507 Number of unrooted triangulations with reflection symmetry of a hexagon with n internal nodes.

Original entry on oeis.org

2, 6, 18, 52, 166, 524, 1722, 5664, 19072, 64408, 220676, 758864, 2634734, 9180872, 32208376, 113371636, 401067522, 1423073892, 5068961452, 18103192360, 64853607912, 232872927444, 838311889890, 3023961593292, 10931277735230, 39586258360246, 143617299291242

Offset: 0

N. J. A. Sloane

nonn

These are also called [n,3]-triangulations.

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..200
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)
C. F. Earl & N. J. A. Sloane, Correspondence, 1980-1981

Column k=3 of the array in A169809.

Cf. A005495, A005502.

a(n) = 2 * A005502(n) - A005495(n) (based on Max Alekseyev's formula, cf. A005500 and A005501).

a(5)-a(10) from Altug Alkan and Manfred Scheucher, Mar 08 2018

Name clarified and terms a(11) and beyond from Andrew Howroyd, Feb 21 2021

A005508 Number of unrooted triangulations with reflection symmetry of a disk with one internal node and n+3 nodes on the boundary.

Original entry on oeis.org

1, 2, 3, 6, 8, 18, 23, 56, 70, 180, 222, 594, 726, 2002, 2431, 6864, 8294, 23868, 28730, 83980, 100776, 298452, 357238, 1069776, 1277788, 3863080, 4605980, 14040810, 16715250, 51325650, 61020495, 188574240, 223931910, 695987820, 825632610, 2579248980

Offset: 0

N. J. A. Sloane

nonn

These are also called [1,n]-triangulations.

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..1000
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)
C. F. Earl & N. J. A. Sloane, Correspondence, 1980-1981

Row n=1 of the array in A169809.

Name clarified and terms a(7) and beyond from Andrew Howroyd, Feb 22 2021

A005509 Number of unrooted triangulations with reflection symmetry of a disk with 2 internal nodes and n+3 nodes on the boundary.

Original entry on oeis.org

1, 4, 7, 18, 26, 68, 91, 248, 318, 900, 1122, 3278, 4004, 12012, 14443, 44304, 52598, 164424, 193154, 613700, 714476, 2302344, 2659582, 8677072, 9954860, 32836180, 37442160, 124715430, 141430680, 475237500, 536257995, 1816267680, 2040199590, 6959878200

Offset: 0

N. J. A. Sloane

nonn

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..500
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)
C. F. Earl & N. J. A. Sloane, Correspondence, 1980-1981

Row n=2 of the array in A169809.

Terms a(6) and beyond from Andrew Howroyd, Feb 22 2021

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A262586 Square array T(n,m) (n>=0, m>=0) read by antidiagonals downwards giving number of rooted triangulations of type [n,m] up to orientation-preserving isomorphisms.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A146305 Array T(n,m) = 2*(2m+3)!*(4n+2m+1)!/(m!*(m+2)!*n!*(3n+2m+3)!) read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A005028 Number of symmetric trivalent maps with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A002712 Number of unrooted triangulations of a disk that have reflection symmetry with n interior nodes and 3 nodes on the boundary.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A005505 Number of unrooted triangulations with reflection symmetry of a quadrilateral with n internal nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A005506 Number of unrooted triangulations with reflection symmetry of a pentagon with n internal nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A005507 Number of unrooted triangulations with reflection symmetry of a hexagon with n internal nodes.

A146305 Array T(n,m) = 2(2m+3)!(4n+2m+1)!/(m!(m+2)!n!*(3n+2m+3)!) read by antidiagonals.