A070765 -id:A070765 - cp's OEIS frontend

A000577 Number of triangular polyominoes (or triangular polyforms, or polyiamonds) with n cells (turning over is allowed, holes are allowed, must be connected along edges).

1, 1, 1, 3, 4, 12, 24, 66, 160, 448, 1186, 3334, 9235, 26166, 73983, 211297, 604107, 1736328, 5000593, 14448984, 41835738, 121419260, 353045291, 1028452717, 3000800627, 8769216722, 25661961898, 75195166667, 220605519559, 647943626796, 1905104762320, 5607039506627, 16517895669575

Offset: 1

N. J. A. Sloane

If holes are not allowed, we get A070765. - Joseph Myers, Apr 20 2009

It is a consequence of Madras's 1999 pattern theorem that almost all polyiamonds have holes, i.e., lim_{n->oo} A070765(n)/A000577(n) = 0. - Johann Peters, Jan 06 2024

F. Harary, Graphical enumeration problems; in Graph Theory and Theoretical Physics, ed. F. Harary, Academic Press, London, 1967, pp. 1-41.
W. F. Lunnon, Counting hexagonal and triangular polyominoes, pp. 87-100 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
Ed Pegg, Jr., Polyform puzzles, in Tribute to a Mathemagician, Peters, 2005, pp. 119-125.
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. J. Torbijn, Polyiamonds, J. Rec. Math., 2 (1969), 216-227.

John Mason, Table of n, a(n) for n = 1..52
Ed Pegg, Jr., Illustrations of polyforms
A. Clarke, Polyiamonds
S. T. Coffin, The Puzzling World of Polyhedral Dissections, Chap 2, Table 1.
R. K. Guy, O'Beirne's Hexiamond, in The Mathemagician and the Pied Puzzler - A Collection in Tribute to Martin Gardner, Ed. E. R. Berlekamp and T. Rogers, A. K. Peters, 1999, 85-96 [broken link?]
J. and J. Hindriks, Dutchman Designs: Quilting Patterns [broken link?]
Kadon Enterprises, The 66 polyominoes of order 8 (from a puzzle)
Kadon Enterprises, Home page
M. Keller, Counting polyforms.
N. Madras, A pattern theorem for lattice clusters, arXiv:math/9902161 [math.PR], 1999; Annals of Combinatorics, 3 (1999), 357-384.
Greg Malen, Érika Roldán, and Rosemberg Toalá-Enríquez, Extremal {p, q}-Animals, Ann. Comb. (2023), p. 3.
John Mason, Counting Polyiamonds
R. J. Mathar, Illustrations for up to 9-iamonds
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
Eric Weisstein's World of Mathematics, Polyiamond

Cf. A000207, A006534, A030223, A030224, A001420, A096361, A070765.

Cf. also A000105, A000228, A103465.

More terms from David W. Wilson
a(19) from Achim Flammenkamp, Feb 15 1999
a(20), a(21), a(22), a(23) and a(24) from Brendan Owen (brendan_owen(AT)yahoo.com), Jan 01 2002
a(25) to a(28) from Joseph Myers, Sep 24 2002
Link updated by William Rex Marshall, Dec 16 2009
a(29) and a(30) from Joseph Myers, Nov 21 2010
More terms from John Mason, Oct 28 2023

A000104 Number of n-celled free polyominoes without holes.

Original entry on oeis.org

1, 1, 1, 2, 5, 12, 35, 107, 363, 1248, 4460, 16094, 58937, 217117, 805475, 3001127, 11230003, 42161529, 158781106, 599563893, 2269506062, 8609442688, 32725637373, 124621833354, 475368834568, 1816103345752, 6948228104703, 26618671505989, 102102788362303

Offset: 0

N. J. A. Sloane

J. S. Madachy, Pentominoes - Some Solved and Unsolved Problems, J. Rec. Math., 2 (1969), 181-188.
George E. Martin, Polyominoes - A Guide to Puzzles and Problems in Tiling, The Mathematical Association of America, 1996
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).

John Mason, Table of n, a(n) for n = 0..40
Elena V. Konstantinova and Maxim V. Vidyuk, Discriminating tests of information and topological indices. Animals and trees, J. Chem. Inf. Comput. Sci. 43 (2003), 1860-1871.
John Mason, Description of counting programs
John Mason, Programs for calculation of numbers of unholey polyominoes
Lucia Moura and Ivan Stojmenovic, Backtracking and Isomorph-Free Generation of Polyhexes, Table 2.2 on p. 55 of Handbook of Applied Algorithms (2008).
W. R. Muller, K. Szymanski, J. V. Knop, and N. Trinajstic, On the number of square-cell configurations, Theor. Chim. Acta 86 (1993) 269-278
Tomás Oliveira e Silva, Enumeration of polyominoes
T. R. Parkin, L. J. Lander, and D. R. Parkin, Polyomino Enumeration Results, presented at SIAM Fall Meeting, 1967, and accompanying letter from T. J. Lander (annotated scanned copy)
R. C. Read, Contributions to the cell growth problem, Canad. J. Math., 14 (1962), 1-20.

Cf. A000105, row sums of A308300, A006746, A056877, A006748, A056878, A006747, A006749, A054361, A070765 (polyiamonds), A018190 (polyhexes), A266549 (by perimeter).

Cf. A056879, A056880, A056881, A056882, A006724, A357647, A357648.

a(n) = A000105(n) - A001419(n). - John Mason, Sep 06 2022

a(n) = (4*A056879(n) + 4*A056881(n) + 4*A056883(n) + 6*A056880(n) + 6*A056882(n) + 6*A357647(n) + 7*A357648(n) + A006724(n)) / 8. - John Mason, Oct 10 2022

Extended to n=26 by Tomás Oliveira e Silva

a(27)-a(28) from Tomás Oliveira e Silva's page added by Andrey Zabolotskiy, Oct 02 2022

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.

Original entry on oeis.org

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

N. J. A. Sloane

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

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

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.

T. D. Noe, Table of n, a(n) for n = 1..200
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, computer printout, circa 1974
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.
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.
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.
Len Smiley, Illustration of initial terms
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]

Column k=3 of A295260.
Cf. A000577, A070765.
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).

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

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

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

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

More terms from James Sellers, Jul 10 2000

cp's OEIS Frontend

A000577 Number of triangular polyominoes (or triangular polyforms, or polyiamonds) with n cells (turning over is allowed, holes are allowed, must be connected along edges).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A000104 Number of n-celled free polyominoes without holes.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A071332 Number of polyiamonds with n cells that tile the plane.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A070764 Number of polyiamonds with n cells, with holes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A071334 Number of polyiamonds with n cells without holes that do not tile the plane.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A341630 Number of fixed polyiamonds of area n without holes.

Views

Author

Keywords

Comments

Links

Crossrefs