|
| |
|
|
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)
|
|
10
| |
|
|
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
(list; graph; refs; listen; history; 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.
C. Ceballos, F. Santos and G. M. Ziegler, Many non-equivalent realizations of the associahedron, Arxiv preprint arXiv:1109.5544, 2011
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.
F. Harary and E. M. Palmer, On acyclic simplicial complexes. Mathematika 15 1968 115-122.
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
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
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
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 (deutsch(AT)duke.poly.edu), 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)) [From M. F. Hasler (www.univ-ag.fr/~mhasler), Apr 19 2009]
|
|
|
EXAMPLE
| E.g. a 4-gon (n=2) could have either diagonal drawn, C(3)=2, but with essentially only one result. A 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 6-gon 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.a - R. K. Guy, Mar 06 2004
|
|
|
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); # [From P. Luschny, Apr 19 2009 and M. F. Hasler (www.univ-ag.fr/~mhasler), 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); (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 (russell(AT)post.harvard.edu), 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}] (* From 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 (www.univ-ag.fr/~mhasler), Apr 19 2009
|
|
|
CROSSREFS
| Cf. A000577, A070765.
A row or column of the array in A169808.
Sequence in context: A111758 A000942 A197459 * A002986 A147569 A090660
Adjacent sequences: A000204 A000205 A000206 * A000208 A000209 A000210
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from James Sellers, Jul 10 2000
|
| |
|
|
