login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 planar 2-trees.
(Formerly M2375 N0942)
11
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 (list; graph; refs; listen; history; text; internal format)
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

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

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

M. Kosters, A theory of hexaflexagons, Nieuw Archief Wisk., 17 (1999), 349-362.

J. W. Moon and L. Moser, Triangular dissections of n-gons, Canad. Math. Bull., 6 (1963), 175-178.

T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360 (the entry for n=10 appears to be incorrect).

C. O. Oakley and R. J. Wisner, Flexagons, Amer. Math. Monthly, 64 (1957), 143-154.

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

T. D. Noe, Table of n, a(n) for n=1..200

Douglas Bowman and Alon Regev, Counting symmetry classes of dissections of a convex regular polygon, arXiv preprint arXiv:1209.6270, 2012.

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, p. 19 and 26

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.

T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.

T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.

Len Smiley, Illustration of initial terms

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

a(n) ~ A000108(n)/(2*n+4) ~ 4^n / (2 sqrt(n Pi)*(n + 1)*(n + 2)). - M. F. Hasler, Apr 19 2009

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

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

Cf. A000577, A070765.

A row or column of the array in A169808.

Sequence in context: A000942 A255436 A197459 * A002986 A147569 A090660

Adjacent sequences:  A000204 A000205 A000206 * A000208 A000209 A000210

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from James A. Sellers, Jul 10 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 22 22:05 EDT 2017. Contains 283901 sequences.