login
A000207
Number of inequivalent ways of dissecting a regular (n+2)-gon into n triangles by n-1 non-intersecting diagonals under rotations and reflections; also the number of (unlabeled) maximal outerplanar graphs on n+2 vertices.
(Formerly M2375 N0942)
23
1, 1, 1, 3, 4, 12, 27, 82, 228, 733, 2282, 7528, 24834, 83898, 285357, 983244, 3412420, 11944614, 42080170, 149197152, 531883768, 1905930975, 6861221666, 24806004996, 90036148954, 327989004892, 1198854697588, 4395801203290, 16165198379984, 59609171366326, 220373278174641
OFFSET
1,4
COMMENTS
Also a(n) is the number of hexaflexagons of order n+2. - Mike Godfrey (m.godfrey(AT)umist.ac.uk), Feb 25 2002 (see the Kosters paper).
Number of normally non-isomorphic realizations of the associahedron of type II with dimension n in Ceballos et al. - Tom Copeland, Oct 19 2011
Number of polyforms with n cells in the hyperbolic tiling with Schläfli symbol {3,oo}, not distinguishing enantiomorphs. - Thomas Anton, Jan 16 2019
A stereographic projection of the {3,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - Robert A. Russell, Jan 20 2024
A maximal outerplanar graph (MOP) has a plane embedding with all vertices on the exterior region and interior regions triangles. - Allan Bickle, Feb 25 2024
REFERENCES
L. W. Beineke and R. E. Pippert, Enumerating labeled k-dimensional trees and ball dissections, pp. 12-26 of Proceedings of Second Chapel Hill Conference on Combinatorial Mathematics and Its Applications, University of North Carolina, Chapel Hill, 1970. Reprinted in Math. Annalen, 191 (1971), 87-98.
Cameron, Peter J. Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155--183. MR0891613 (89a:05009). See pp. 155, 163, but note that the formulas on p. 163, lines 5 and 6, contain typos. See the correct formulas given here. - N. J. A. Sloane, Apr 18 2014
B. N. Cyvin, E. Brendsdal, J. Brunvoll and S. J. Cyvin, Isomers of polyenes attached to benzene, Croatica Chemica Acta, 68 (1995), 63-73.
S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, Enumeration of polyene hydrocarbons: a complete mathematical solution, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751.
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.
R. K. Guy, "Dissecting a polygon into triangles," Bull. Malayan Math. Soc., Vol. 5, pp. 57-60, 1958.
R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 79, Table 3.5.1 (the entries for n=16 and n=21 appear to be incorrect).
M. Kosters, A theory of hexaflexagons, Nieuw Archief Wisk., 17 (1999), 349-362.
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).
P. K. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
LINKS
F. R. Bernhart & N. J. A. Sloane, Correspondence, 1977
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
Douglas Bowman and Alon Regev, Counting symmetry classes of dissections of a convex regular polygon, arXiv preprint arXiv:1209.6270 [math.CO], 2012.
William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 160.
C. Ceballos, F. Santos, and G. Ziegler, Many Non-equivalent Realizations of the Associahedron, arXiv:1109.5544 [math.MG], 2011-2013, p. 19 and 26.
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
Sean Cleary, Roland Maio, Counting difficult tree pairs with respect to the rotation distance problem, arXiv:2001.06407 [cs.DS], 2020.
A. S. Conrad and D. K. Hartline, Flexagons
S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, Enumeration of polyene hydrocarbons: a complete mathematical solution, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751. [Annotated scanned copy]
R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967. [Annotated scanned copy]
F. Harary and E. M. Palmer, On acyclic simplicial complexes, Mathematika 15 1968 115-122.
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389 (the entries for n=4 and n=30 appear to be incorrect).
J. W. Moon and L. Moser, Triangular dissections of n-gons, Canad. Math. Bull., 6 (1963), 175-178.
T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
C. O. Oakley and R. J. Wisner, Flexagons, Amer. Math. Monthly 64 (1957), 143-154.
Hans Rademacher, On the number of certain types of polyhedra, Illinois Journal of Mathematics 9.3 (1965): 361-380. Reprinted in Coll. Papers, Vol II, MIT Press, 1974, pp. 544-564.
Manfred Scheucher, Hendrik Schrezenmaier, Raphael Steiner, A Note On Universal Point Sets for Planar Graphs, arXiv:1811.06482 [math.CO], 2018.
Tiberiu Spircu and Stefan V. Pantazi, Again around frieze patterns, arXiv:2002.08211 [math.CO], 2020. See Kn p. 13.
P. J. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974. [Scanned annotated and corrected copy]
FORMULA
a(n) = C(n)/(2*n) + C(n/2+1)/4 + C(k)/2 + C(n/3+1)/3 where C(n) = A000108(n-2) if n is an integer, 0 otherwise and k = (n+1)/2 if n is odd, k = n/2+1 if n is even. Thus C(2), C(3), C(4), C(5), ... are 1, 1, 2, 5, ...
G.f.: (12*(1+x-2*x^2) + (1-4*x)^(3/2) - 3*(3+2*x)*(1-4*x^2)^(1/2) - 4*(1-4*x^3)^(1/2))/(24*x^2). - Emeric Deutsch, Dec 19 2004, from the S. J. Cyvin et al. reference.
a(n) ~ A000108(n)/(2*n+4) ~ 4^n / (2 sqrt(n Pi)*(n + 1)*(n + 2)). - M. F. Hasler, Apr 19 2009
a(n) = A001683(n+2) - A369314(n) = (A001683(n+2) + A208355(n-1)) / 2 = A369314(n) + A208355(n-1). - Robert A. Russell, Jan 19 2024
Beineke and Pippert have an explicit formula with six cases (based on the value of n mod 6). - Allan Bickle, Feb 25 2024
EXAMPLE
E.g., a square (4-gon, n=2) could have either diagonal drawn, C(3)=2, but with essentially only one result. A pentagon (5-gon, n=3) gives C(4)=5, but they each have 2 diags emanating from 1 of the 5 vertices and are essentially the same. A hexagon can have a nuclear disarmament sign (6 ways), an N (3 ways and 3 reflections) or a triangle (2 ways) of diagonals, 6 + 6 + 2 = 14 = C(5), but only 3 essentially different. - R. K. Guy, Mar 06 2004
G.f. = x + x^2 + x^3 + 3*x^4 + 4*x^5 + 12*x^6 + 27*x^7 + 82*x^8 + ...
MAPLE
A000108 := proc(n) if n >= 0 then binomial(2*n, n)/(n+1) ; else 0; fi; end:
A000207 := proc(n) option remember: local k, it1, it2;
if n mod 2 = 0 then k := n/2+2 else k := (n+3)/2 fi:
if n mod 2 <> 0 then it1 := 0 else it1 := 1 fi:
if (n+2) mod 3 <> 0 then it2 := 0 else it2 := 1 fi:
RETURN(A000108(n)/(2*n+4) + it1*A000108(n/2)/4 + A000108(k-2)/2 + it2*A000108((n-1)/3)/3)
end:
seq(A000207(n), n=1..30) ; # (Revised Maple program from R. J. Mathar, Apr 19 2009)
A000207 := proc(n) option remember: local k, it1, it2; if n mod 2 = 0 then k := n/2+1 else k := (n+1)/2 fi: if n mod 2 <> 0 then it1 := 0 else it1 := 1 fi: if n mod 3 <> 0 then it2 := 0 else it2 := 1 fi: RETURN(A000108(n-2)/(2*n) + it1*A000108(n/2+1-2)/4 + A000108(k-2)/2 + it2*A000108(n/3+1-2)/3) end:
A000207 := n->(A000108(n)/(n+2)+A000108(floor(n/2))*((1+(n+1 mod 2) /2)))/2+`if`(n mod 3=1, A000108(floor((n-1)/3))/3, 0); # Peter Luschny, Apr 19 2009 and M. F. Hasler, Apr 19 2009
G:=(12*(1+x-2*x^2)+(1-4*x)^(3/2)-3*(3+2*x)*(1-4*x^2)^(1/2)-4*(1-4*x^3)^(1/2))/24/x^2: Gser:=series(G, x=0, 35): seq(coeff(Gser, x^n), n=1..31); # Emeric Deutsch, Dec 19 2004
MATHEMATICA
p=3; Table[(Binomial[(p-1)n, n]/(((p-2)n+1)((p-2)n+2)) + If[OddQ[n], If[OddQ[p], Binomial[(p-1)n/2, (n-1)/2]/n, (p+1)Binomial[((p-1)n-1)/2, (n-1)/2]/((p-2)n+2)], 3Binomial[(p-1)n/2, n/2]/((p-2)n+2)]+Plus @@ Map[EulerPhi[ # ]Binomial[((p-1)n+1)/#, (n-1)/# ]/((p-1)n+1)&, Complement[Divisors[GCD[p, n-1]], {1, 2}]])/2, {n, 1, 20}] (* Robert A. Russell, Dec 11 2004 *)
a[n_] := (CatalanNumber[n]/(n+2) + CatalanNumber[ Quotient[n, 2]] *((1 + Mod[n-1, 2]/2)))/2 + If[Mod[n, 3] == 1, CatalanNumber[ Quotient[n-1, 3]]/3, 0] ; Table[a[n], {n, 1, 28}] (* Jean-François Alcover, Sep 08 2011, after PARI *)
PROG
(PARI) A000207(n)=(A000108(n)/(n+2)+A000108(n\2)*if(n%2, 1, 3/2))/2+if(n%3==1, A000108(n\3)/3) \\ M. F. Hasler, Apr 19 2009
CROSSREFS
Column k=3 of A295260.
A row or column of the array in A169808.
Polyominoes: A001683(n+2) (oriented), A369314 (chiral), A208355(n-1) (achiral), A005036 {4,oo}, A007173 {3,3,oo}.
Cf. A097998, A097999, A098000 (labeled outerplanar graphs).
Cf. A111563, A111564, A111758, A111759, A111757 (unlabeled outerplanar graphs).
Sequence in context: A255436 A197459 A330659 * A002986 A147569 A090660
KEYWORD
nonn,nice,easy
EXTENSIONS
More terms from James A. Sellers, Jul 10 2000
STATUS
approved