|
%I M2375 N0942 #135 Feb 26 2024 09:19:12
%S 1,1,1,3,4,12,27,82,228,733,2282,7528,24834,83898,285357,983244,
%T 3412420,11944614,42080170,149197152,531883768,1905930975,6861221666,
%U 24806004996,90036148954,327989004892,1198854697588,4395801203290,16165198379984,59609171366326,220373278174641
%N 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.
%C 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).
%C Number of normally non-isomorphic realizations of the associahedron of type II with dimension n in Ceballos et al. - _Tom Copeland_, Oct 19 2011
%C Number of polyforms with n cells in the hyperbolic tiling with Schläfli symbol {3,oo}, not distinguishing enantiomorphs. - _Thomas Anton_, Jan 16 2019
%C 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
%C 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
%D 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.
%D 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
%D B. N. Cyvin, E. Brendsdal, J. Brunvoll and S. J. Cyvin, Isomers of polyenes attached to benzene, Croatica Chemica Acta, 68 (1995), 63-73.
%D 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.
%D 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.
%D R. K. Guy, "Dissecting a polygon into triangles," Bull. Malayan Math. Soc., Vol. 5, pp. 57-60, 1958.
%D R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967.
%D 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).
%D M. Kosters, A theory of hexaflexagons, Nieuw Archief Wisk., 17 (1999), 349-362.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D 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.
%H T. D. Noe, <a href="/A000207/b000207.txt">Table of n, a(n) for n = 1..200</a>
%H F. R. Bernhart & N. J. A. Sloane, <a href="/A001683/a001683.pdf">Correspondence, 1977</a>
%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.
%H Douglas Bowman and Alon Regev, <a href="http://arxiv.org/abs/1209.6270">Counting symmetry classes of dissections of a convex regular polygon</a>, arXiv preprint arXiv:1209.6270 [math.CO], 2012.
%H William G. Brown, <a href="http://dx.doi.org/10.1112/plms/s3-14.4.746">Enumeration of Triangulations of the Disk</a>, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.
%H P. J. Cameron, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H P. J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 160.
%H C. Ceballos, F. Santos, and G. Ziegler, <a href="http://arxiv.org/abs/1109.5544">Many Non-equivalent Realizations of the Associahedron</a>, arXiv:1109.5544 [math.MG], 2011-2013, p. 19 and 26.
%H Malin Christensson, <a href="http://malinc.se/m/ImageTiling.php">Make hyperbolic tilings of images</a>, web page, 2019.
%H Sean Cleary, Roland Maio, <a href="https://arxiv.org/abs/2001.06407">Counting difficult tree pairs with respect to the rotation distance problem</a>, arXiv:2001.06407 [cs.DS], 2020.
%H A. S. Conrad and D. K. Hartline, <a href="http://theory.lcs.mit.edu/~edemaine/flexagons/Conrad-Hartline-1962/flexagon.html">Flexagons</a>
%H S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, <a href="/A002057/a002057.pdf">Enumeration of polyene hydrocarbons: a complete mathematical solution</a>, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751. [Annotated scanned copy]
%H R. K. Guy, <a href="/A000108/a000108_11.pdf">Dissecting a polygon into triangles</a>, Research Paper #9, Math. Dept., Univ. Calgary, 1967. [Annotated scanned copy]
%H F. Harary and E. M. Palmer, <a href="http://dx.doi.org/10.1112/S002557930000245X">On acyclic simplicial complexes</a>, Mathematika 15 1968 115-122.
%H F. Harary, E. M. Palmer, and R. C. Read, <a href="/A000108/a000108_20.pdf">On the cell-growth problem for arbitrary polygons, computer printout, circa 1974</a>
%H F. Harary, E. M. Palmer and R. C. Read, <a href="http://dx.doi.org/10.1016/0012-365X(75)90041-2">On the cell-growth problem for arbitrary polygons</a>, Discr. Math. 11 (1975), 371-389 (the entries for n=4 and n=30 appear to be incorrect).
%H J. W. Moon and L. Moser, <a href="https://doi.org/10.4153/CMB-1963-017-0">Triangular dissections of n-gons</a>, Canad. Math. Bull., 6 (1963), 175-178.
%H T. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1945-08486-9">The hypersurface cross ratio</a>, Bull. Amer. Math. Soc., 51 (1945), 976-984.
%H T. S. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1948-09002-4 ">Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products</a>, Bull. Amer. Math. Soc., 54 (1948), 352-360 (the entry for n=10 appears to be incorrect).
%H C. O. Oakley and R. J. Wisner, <a href="http://www.jstor.org/stable/2310544">Flexagons</a>, Amer. Math. Monthly 64 (1957), 143-154.
%H Hans Rademacher, <a href="https://doi.org/10.1215/ijm/1256068140">On the number of certain types of polyhedra</a>, Illinois Journal of Mathematics 9.3 (1965): 361-380. Reprinted in Coll. Papers, Vol II, MIT Press, 1974, pp. 544-564.
%H Manfred Scheucher, Hendrik Schrezenmaier, Raphael Steiner, <a href="https://arxiv.org/abs/1811.06482">A Note On Universal Point Sets for Planar Graphs</a>, arXiv:1811.06482 [math.CO], 2018.
%H Len Smiley, <a href="/A000207/a000207.jpg">Illustration of initial terms</a>
%H Tiberiu Spircu and Stefan V. Pantazi, <a href="https://arxiv.org/abs/2002.08211">Again around frieze patterns</a>, arXiv:2002.08211 [math.CO], 2020. See Kn p. 13.
%H P. J. Stockmeyer, <a href="/A006078/a006078.pdf">The charm bracelet problem and its applications</a>, 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]
%F 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, ...
%F G.f.: (12(1+x-2x^2) + (1-4x)^(3/2) - 3(3+2x)(1-4x^2)^(1/2) - 4(1-4x^3)^(1/2)]/(24x^2). - _Emeric Deutsch_, Dec 19 2004, from the S. J. Cyvin et al. reference.
%F a(n) ~ A000108(n)/(2*n+4) ~ 4^n / (2 sqrt(n Pi)*(n + 1)*(n + 2)). - _M. F. Hasler_, Apr 19 2009
%F 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
%F Beineke and Pippert have an explicit formula with six cases (based on the value of n mod 6). - _Allan Bickle_, Feb 25 2024
%e 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
%e G.f. = x + x^2 + x^3 + 3*x^4 + 4*x^5 + 12*x^6 + 27*x^7 + 82*x^8 + ...
%p A000108 := proc(n) if n >= 0 then binomial(2*n,n)/(n+1) ; else 0; fi; end:
%p A000207 := proc(n) option remember: local k, it1, it2;
%p if n mod 2 = 0 then k := n/2+2 else k := (n+3)/2 fi:
%p if n mod 2 <> 0 then it1 := 0 else it1 := 1 fi:
%p if (n+2) mod 3 <> 0 then it2 := 0 else it2 := 1 fi:
%p RETURN(A000108(n)/(2*n+4) + it1*A000108(n/2)/4 + A000108(k-2)/2 + it2*A000108((n-1)/3)/3)
%p end:
%p seq(A000207(n),n=1..30) ; # (Revised Maple program from _R. J. Mathar_, Apr 19 2009)
%p 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:
%p 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
%p 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
%t 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 *)
%t 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 *)
%o (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
%Y Column k=3 of A295260.
%Y Cf. A000577, A070765.
%Y A row or column of the array in A169808.
%Y Polyominoes: A001683(n+2) (oriented), A369314 (chiral), A208355(n-1) (achiral), A005036 {4,oo}, A007173 {3,3,oo}.
%Y Cf. A097998, A097999, A098000 (labeled outerplanar graphs).
%Y Cf. A111563, A111564, A111758, A111759, A111757 (unlabeled outerplanar graphs).
%K nonn,nice,easy
%O 1,4
%A _N. J. A. Sloane_
%E More terms from _James A. Sellers_, Jul 10 2000
|
