A002216 -id:A002216 - cp's OEIS frontend

A002212 Number of restricted hexagonal polyominoes with n cells.

1, 1, 3, 10, 36, 137, 543, 2219, 9285, 39587, 171369, 751236, 3328218, 14878455, 67030785, 304036170, 1387247580, 6363044315, 29323149825, 135700543190, 630375241380, 2938391049395, 13739779184085, 64430797069375, 302934667061301, 1427763630578197

Offset: 0

N. J. A. Sloane, Ronald C. Read

Number of Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1), H=(2,0) and never going below the x-axis) from (0,0) to (2n,0) with no peaks at odd level. Example: a(2)=3 because we have UUDD, UHD and HH. - Emeric Deutsch, Dec 06 2003
Number of 3-Motzkin paths of length n-1 (i.e., lattice paths from (0,0) to (n-1,0) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and three types of steps H=(1,0)). Example: a(4)=36 because we have 27 HHH paths, 3 HUD paths, 3 UHD paths and 3 UDH paths. - Emeric Deutsch, Jan 22 2004
Number of rooted, planar trees having edges weighted by strictly positive integers (multi-trees) with weight-sum n. - Roland Bacher, Feb 28 2005
Number of skew Dyck paths of semilength n. A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps. - Emeric Deutsch, May 10 2007
Equivalently, number of self-avoiding paths of semilength n in the first quadrant beginning at the origin, staying weakly above the diagonal, ending on the diagonal, and consisting of steps r=(+1,0) (right), U=(0,+1) (up), and D=(0,-1) (down). Self-avoidance implies that factors UD and DU and steps D reaching the diagonal before the end are forbidden. The a(3) = 10 such paths are UrUrUr, UrUUrD, UrUUrr, UUrrUr, UUrUrD, UUrUrr, UUUDrD, UUUrDD, UUUrrD, and UUUrrr. - Joerg Arndt, Jan 15 2024
Hankel transform of [1,3,10,36,137,543,...] is A000012 = [1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
From Gary W. Adamson, May 17 2009: (Start)
Convolved with A026375, (1, 3, 11, 45, 195, ...) = A026378: (1, 4, 17, 75, ...)
(1, 3, 10, 36, 137, ...) convolved with A026375 = A026376: (1, 6, 30, 144, ...).
Starting (1, 3, 10, 36, ...) = INVERT transform of A007317: (1, 2, 5, 15, 51, ...). (End)
Binomial transform of A032357. - Philippe Deléham, Sep 17 2009
a(n) = number of rooted trees with n vertices in which each vertex has at most 2 children and in case a vertex has exactly one child, it is labeled left, middle or right. These are the hex trees of the Deutsch, Munarini, Rinaldi link. This interpretation yields the second MATHEMATICA recurrence below. - David Callan, Oct 14 2012
The left shift (1,3,10,36,...) of this sequence is the binomial transform of the left-shifted Catalan numbers (1,2,5,14,...). Example: 36 =1*14 + 3*5 + 3*2 + 1*1. - David Callan, Feb 01 2014
Number of Schroeder paths from (0,0) to (2n,0) with no level steps H=(2,0) at even level. Example: a(2)=3 because we have UUDD, UHD and UDUD. - José Luis Ramírez Ramírez, Apr 27 2015
This is the Riordan transform with the Riordan matrix A097805 (of the associated type) of the Catalan sequence A000108. See a Feb 17 2017 comment in A097805. - Wolfdieter Lang, Feb 17 2017
a(n) is the number of parking functions of size n avoiding the patterns 132 and 231. - Lara Pudwell, Apr 10 2023

			G.f. = 1 + x + 3*x^2 + 10*x^3 + 36*x^4 + 137*x^5 + 543*x^6 + 2219*x^7 + 9285*x^8 + ...

J. Brunvoll, B. N. Cyvin, and S. J. Cyvin, Studies of some chemically relevant polygonal systems: mono-q-polyhexes, ACH Models in Chem., 133 (3) (1996), 277-298, Eq 14.
S. J. Cyvin, J. Brunvoll, G. Xiaofeng, and Z. Fuji, Number of perifusenes with one internal vertex, Rev. Roumaine Chem., 38(1) (1993), 65-78.
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).

T. D. Noe, Table of n, a(n) for n = 0..200
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Jean-Luc Baril, José L. Ramírez, and Lina M. Simbaqueba, Counting prefixes of skew Dyck paths, J. Int. Seq., Vol. 24 (2021), Article 21.8.2.
L. W. Beineke and R. E. Pippert, On the enumeration of planar trees of hexagons, Glasgow Math. J., 15 (1974), 131-147. See V(n).
L. W. Beineke and R. E. Pippert, On the enumeration of planar trees of hexagons, Glasgow Math. J., 15 (1974), 131-147. [Annotated scanned copy]
Johann Cigler and Christian Krattenthaler, Hankel determinants of linear combinations of moments of orthogonal polynomials, arXiv:2003.01676 [math.CO], 2020.
B. N. Cyvin et al., A class of polygonal systems representing polycyclic conjugated hydrocarbons: Catacondensed monoheptafusenes, Monat. f. Chemie, 125 (1994), 1327-1337 (see U(x)).
S. J. Cyvin, J. Brunvoll, and B. N. Cyvin, Harary-Read numbers for catafusenes: Complete classification according to symmetry, Journal of mathematical chemistry 9.1 (1992): 19-31.
S. J. Cyvin and J. Brunvoll, Generating functions for the Harary-Read numbers classified according to symmetry, Journal of mathematical chemistry 9.1 (1992): 33-38.
S. J. Cyvin et al., Graph-theoretical studies on fluoranthenoids and fluorenoids:enumeration of some catacondensed systems, J. Molec. Struct. (Theochem), 285 (1993), 179-185.
S. J. Cyvin et al., Enumeration and classification of certain polygonal systems representing polycyclic conjugated hydrocarbons: annelated catafusenes, J. Chem. Inform. Comput. Sci., 34 (1994), 1174-1180.
D. E. Davenport, L. W. Shapiro, and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012
Rodrigo De Castro, Andrés Ramírez, and José L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449 [cs.DM], 2013. See also Sci. Annals Comp. Sci. (2014) Vol. XXIV, Issue 1, 137-171. See p. 141.
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Serkan Demiriz, Adem Şahin, and Sezer Erdem, Some topological and geometric properties of novel generalized Motzkin sequence spaces, Rendiconti Circ. Mat. Palermo Ser. 2 (2025) Vol. 74, No. 136. See p. 4.
Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.
E. Deutsch, E. Munarini, and S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203
M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 18.
N. S. S. Gu, N. Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.
C. Heuberger, H. Prodinger, and S. Wagner, The height of multiple edge plane trees, arXiv preprint arXiv:1503.04749 [math.CO], 2015.
P.-Y. Huang, S.-C. Liu, and Y.-N. Yeh, Congruences of Finite Summations of the Coefficients in certain Generating Functions, The Electronic Journal of Combinatorics, 21 (2014), #P2.45.
C. Jean-Louis and A. Nkwanta, Some algebraic structure of the Riordan group, Linear Algebra and its Applications, Nov. 27, 2012. - _N. J. A. Sloane_, Jan 03 2013
Hana Kim and R. P. Stanley, A refined enumeration of hex trees and related polynomials, Preprint 2015.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see pp. 12-13.
Lily L. Liu, Positivity of three-term recurrence sequences, Electronic J. Combinatorics, 17 (2010), #R57.
Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
Toufik Mansour and Jose Luis Ramirez, Enumration of Fuss-skew paths, Ann. Math. Inform. 55 (2022) 125-136, table 1.
Michal Medek, Möbius function of matrix posets, Bachelor Thesis, Charles Univ. (Prague, Czechia 2023).
H. D. Nguyen and D. Taggart, Mining the OEIS: Ten Experimental Conjectures, 2013; http://citeseerx.ist.psu.edu/pdf/8f2f36f22878c984775ed04368b8893879b99458. Mentions this sequence. - From _N. J. A. Sloane_, Mar 16 2014
F. Pakovich and A. K. Zvonkin, Minimum degree of the difference of two polynomials over Q, and weighted plane trees, arXiv:1306.4141 [math.NT], 2013.
F. Pakovich and A. K. Zvonkin, Minimum degree of the difference of two polynomials over Q, and weighted plane trees, Selecta Mathematica, New Ser. 2014.
J.-B. Priez, A lattice of combinatorial Hopf algebras, Application to binary trees with multiplicities, arXiv preprint arXiv:1303.5538 [math.CO], 2013.
J.-B. Priez, A lattice of combinatorial Hopf algebras, Application to binary trees with multiplicities, FPSAC 2013 Paris, France DMTCS Proc. AS, 2013, 1167-1179. See also DOI
Helmut Prodinger, Weighted unary-binary trees, Hex-trees, and Horton-Strahler numbers revisited, arXiv:2106.14782 [math.CO], 2021.
Helmut Prodinger, Multi-edge trees and 3-coloured Motzkin paths: bijective issues, arXiv:2105.03350 [math.CO], 2021.
Helmut Prodinger, Partial skew Dyck paths---a kernel method approach, arXiv:2108.09785 [math.CO], 2021.
Helmut Prodinger, Prefixes of Stanley's Catalan paths with odd returns to the x-axis -- standard version and skew Catalan-Stanley paths, arXiv:2402.01429 [math.CO], 2023.
R. C. Read, Letter to N. J. A. Sloane, Feb 12 1971 (includes 40 terms of A002212 and A002216)
E. Rowland and R. Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635 [math.NT], 2013.
A. Sapounakis and P. Tsikouras, On k-colored Motzkin words, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.5.
R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1.
Hua Sun and Yi Wang, A Combinatorial Proof of the Log-Convexity of Catalan-Like Numbers, J. Int. Seq. 17 (2014) # 14.5.2.
Y. Sun and Z. Wang, Consecutive pattern avoidances in non-crossing trees, Graph. Combinat. 26 (2010) 815-832, table 1, {uu,ud}
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.
Y. Wang and Z.-H. Zhang, Combinatorics of Generalized Motzkin Numbers, J. Int. Seq. 18 (2015) # 15.2.4.
E. X. W. Xia and O. X. M. Yao, A Criterion for the Log-Convexity of Combinatorial Sequences, The Electronic Journal of Combinatorics, 20 (2013), #P3.
A. K. Zvonkin, Enumeration of Weighted Plane Trees, 2013.
Index entries for reversions of series

Cf. A025238, A000108, A001006, A007317, A026376, A026375.
First differences of A007317.
Row sums of triangle A104259.
Cf. A005572, A025230, A182401.

I:= [1,3]; [1] cat [n le 2 select I[n]  else ((6*n-3)*Self(n-1)-5*(n-2)*Self(n-2)) div (n+1): n in [1..30]]; // Vincenzo Librandi, Jun 15 2015

t1 := series(1+ (1-3*x-(1-x)^(1/2)*(1-5*x)^(1/2))/(2*x), x, 50):
A002212_list := len -> seq(coeff(t1,x,n),n=0..len): A002212_list(40);
a[0] := 1: a[1] := 1: for n from 2 to 50 do a[n] := (3*(2*n-1)*a[n-1]-5*(n-2)*a[n-2])/(n+1) od: print(convert(a,list)); # Zerinvary Lajos, Jan 01 2007
a := n -> `if`(n=0,1,simplify(GegenbauerC(n-1, -n, -3/2)/n)):
seq(a(n), n=0..23); # Peter Luschny, May 09 2016

InverseSeries[Series[(y)/(1+3*y+y^2), {y, 0, 24}], x] (* then A(x)=1+y(x) *) (* Len Smiley, Apr 14 2000 *)
(* faster *)
a[0]=1;a[1]=1;
a[n_]/;n>=2 := a[n] = a[n-1] +  Sum[a[i]a[n-1-i],{i,0,n-1}];
Table[a[n],{n,0,14}] (* See COMMENTS above, [David Callan, Oct 14 2012] *)
(* fastest *)
s[0]=s[1]=1;
s[n_]/;n>=2 := s[n] = (3(2n-1)s[n-1]-5(n-2)s[n-2])/(n+1);
Table[s[n],{n,0,14 }] (* See Deutsch, Munarini, Rinaldi link, [David Callan, Oct 14 2012] *)
(* 2nd fastest *)
a[n_] := Hypergeometric2F1[3/2, 1-n, 3, -4]; a[0]=1; Table[a[n], {n, 0, 14}]  (* Jean-François Alcover, May 16 2013 *)
CoefficientList[Series[(1 - x - Sqrt[1 - 6x + 5x^2])/(2x), {x, 0, 20}], x] (* Nikolaos Pantelidis, Jan 30 2023 *)

makelist(sum(binomial(n,k)*binomial(n-k,k)*3^(n-2*k)/(k+1),k,0,n/2),n,0,24); /* for a(n+1) */ /* Emanuele Munarini, May 18 2011 */

{a(n) = polcoeff( (1 - x - sqrt(1 - 6*x + 5*x^2 + x^2 * O(x^n))) / 2, n+1)};

{a(n) = if( n<1, n==0, polcoeff( serreverse( x / (1 + 3*x + x^2) + x * O(x^n)), n))}; /* Michael Somos */

my(N=66,x='x+O('x^N)); Vec((1 - x - sqrt(1-6*x+5*x^2))/(2*x)) \\ Joerg Arndt, Jan 13 2024

def A002212():
    x, y, n = 1, 1, 1
    while True:
        yield x
        n += 1
        x, y = y, ((6*n - 3)*y - (5*n - 10)*x) / (n + 1)
a = A002212()
[next(a) for i in range(24)]  # Peter Luschny, Oct 12 2013

a(0)=1, for n > 0: a(n) = Sum_{j=0..n-1} Sum_{i=0..j} a(i)*a(j-i). G.f.: A(x) = 1 + x*A(x)^2/(1-x). - Mario Catalani (mario.catalani(AT)unito.it), Jun 19 2003
a(n) = Sum_{i=ceiling((n-1)/2)..n-1} (3^(2i+1-n)*binomial(n, i)*binomial(i, n-i-1))/n. - Emeric Deutsch, Jul 23 2002
a(n) = Sum_{k=1..n} binomial(2k, k)*binomial(n-1, k-1)/(k+1), i.e., binomial transform of the Catalan numbers 1, 2, 5, 14, 42, ... (A000108). a(n) = Sum_{k=0..floor((n-1)/2)} 3^(n-1-2*k)*binomial(2k, k)*binomial(n-1, 2k)/(k+1). - Emeric Deutsch, Aug 05 2002
D-finite with recurrence: a(1)=1, a(n) = (3(2n-1)*a(n-1)-5(n-2)*a(n-2))/(n+1) for n > 1. - Emeric Deutsch, Dec 18 2002
a(n) is asymptotic to c*5^n/n^(3/2) with c=0.63.... - Benoit Cloitre, Jun 23 2003
In closed form, c = (1/2)*sqrt(5/Pi) = 0.63078313050504... - Vaclav Kotesovec, Oct 04 2012
Reversion of Sum_{n>0} a(n)x^n = -Sum_{n>0} A001906(n)(-x)^n.
G.f. A(x) satisfies xA(x)^2 + (1-x)(1-A(x)) = 0.
G.f.: (1 - x - sqrt(1 - 6x + 5x^2))/(2x). For n > 1, a(n) = 3*a(n-1) + Sum_{k=1..n-2} a(k)*a(n-k-1). - John W. Layman, Feb 22 2001
The Hankel transform of this sequence gives A001519 = 1, 2, 5, 13, 34, 89, ... E.g., Det([1, 1, 3, 10, 36; 1, 3, 10, 36, 137; 3, 10, 36, 137, 543; 10, 36, 137, 543, 2219; 36, 137, 543, 2219, 9285 ])= 34. - Philippe Deléham, Jan 25 2004
a(m+n+1) = Sum_{k>=0} A091965(m, k)*A091965(n, k) = A091965(m+n, 0). - Philippe Deléham, Sep 14 2005
a(n+1) = Sum_{k=0..n} 2^(n-k)*M(k)*binomial(n,k), where M(k) = A001006(k) is the k-th Motzkin number (from here it follows that a(n+1) and M(n) have the same parity). - Emeric Deutsch, May 10 2007
a(n+1) = Sum_{k=0..n} A097610(n,k)*3^k. - Philippe Deléham, Oct 02 2007
G.f.: 1/(1-x/(1-x-x/(1-x/(1-x-x/(1-x/(1-x-x/(1-... (continued fraction). - Paul Barry, May 16 2009
G.f.: (1-x)/(1-2x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-.... (continued fraction). - Paul Barry, Oct 17 2009
G.f.: 1/(1-z/(1-z/(1-z/(...)))) where z=x/(1-x) (continued fraction); more generally g.f. C(x/(1-x)) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011
a(n) = -5^(1/2)/(10*(n+1)) * (5*hypergeom([1/2, n], [1], 4/5) -3*hypergeom([1/2, n+1], [1], 4/5)) (for n>0). - Mark van Hoeij, Nov 12 2009
For n >= 1, a(n) = (1/(2*Pi))*Integral_{x=1..5} x^(n-1)*sqrt((x-1)*(5-x)) dx. - Groux Roland, Mar 16 2011
a(n+1) = [x^n](1-x^2)(1+3*x+x^2)^n. - Emanuele Munarini, May 18 2011
From Gary W. Adamson, Jul 21 2011: (Start)
a(n) = upper left term in M^(n-1), M = an infinite square production matrix as follows (with 3,2,2,2,... as the main diagonal):
  3, 1, 0, 0, 0, 0, ...
  1, 2, 1, 0, 0, 0, ...
  1, 1, 2, 1, 0, 0, ...
  1, 1, 1, 2, 1, 0, ...
  1, 1, 1, 1, 2, 0, ...
  ...
Alternatively, let M = the previous matrix but change the 3 to a 2. Then a(n) = sum of top row terms of M^(n-1). (End)
a(n) = hypergeometric([1-n,3/2],[3],-4), for n>0. - Peter Luschny, Aug 15 2012
a(n) = GegenbauerC(n-1, -n, -3/2)/n for n >= 1. - Peter Luschny, May 09 2016
E.g.f.: 1 + Integral (exp(3*x) * BesselI(1,2*x) / x) dx. - Ilya Gutkovskiy, Jun 01 2020
G.f.: 1 + x/G(0) with G(k) = (1 - 3*x - x^2/G(k+1)) (continued fraction). - Nikolaos Pantelidis, Dec 12 2022
From Peter Bala, Feb 03 2024: (Start)
G.f.: 1 + x/(1 - x) * c(x/(1 - x))^2 = 1 + x/(1 - 5*x) * c(-x/(1 - 5*x))^2, where c(x) = (1  - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108.
a(n+1) = Sum_{k = 0..n} binomial(n, k)*Catalan(k+1).
a(n+1) = hypergeom([-n, 3/2], [3], -4).
a(n+1) = 5^n * Sum_{k = 0..n} (-5)^(-k)*binomial(n, k)*Catalan(k+1).
a(n+1) = 5^n * hypergeom([-n, 3/2], [3], 4/5). (End)

A000228 Number of hexagonal polyominoes (or hexagonal polyforms, or planar polyhexes) with n cells.

Original entry on oeis.org

1, 1, 3, 7, 22, 82, 333, 1448, 6572, 30490, 143552, 683101, 3274826, 15796897, 76581875, 372868101, 1822236628, 8934910362, 43939164263, 216651036012, 1070793308942, 5303855973849, 26323064063884, 130878392115834, 651812979669234, 3251215493161062, 16240020734253127, 81227147768301723, 406770970805865187, 2039375198751047333

Offset: 1

N. J. A. Sloane

From Markus Voege, Nov 24 2009: (Start)
On the difference between this sequence and A038147:
The first term that differs is for n=6; for all subsequent terms, the number of polyhexes is larger than the number of planar polyhexes.
If I recall correctly, polyhexes are clusters of regular hexagons that are joined at the edges and are LOCALLY embeddable in the hexagonal lattice.
"Planar polyhexes" are polyhexes that are GLOBALLY embeddable in the honeycomb lattice.
Example: (Planar) polyhex with 6 cells (x) and a hole (O):
.. x x
. x O x
.. x x
Polyhex with 6 cells that is cut open (I):
.. xIx
. x O x
.. x x
This polyhex is not globally embeddable in the honeycomb lattice, since adjacent cells of the lattice must be joined. But it can be embedded locally everywhere. It is a start of a spiral. For n>6 the spiral can be continued so that the cells overlap.
Illegal configuration with cut (I):
.. xIx
. x x x
.. x x
This configuration is NOT a polyhex since the vertex at
.. xIx
... x
is not embeddable in the honeycomb lattice.
One has to keep in mind that these definitions are inspired by chemistry. Hence, potential molecules are often the motivation for these definitions. Think of benzene rings that are fused at a C-C bond.
The (planar) polyhexes are "free" configurations, in contrast to "fixed" configurations as in A001207 = Number of fixed hexagonal polyominoes with n cells.
A000228 (planar polyhexes) and A001207 (fixed hexagonal polyominoes) differ only by the attribute "free" vs. "fixed," that is, whether the different orientations and reflections of an embedding in the lattice are counted.
The configuration
. x x .... x
.. x .... x x
is counted once as free and twice as fixed configurations.
Since most configurations have no symmetry, (A001207 / A000228) -> 12 for n -> infinity. (End)

A. T. Balaban and F. Harary, Chemical graphs V: enumeration and proposed nomenclature of benzenoid cata-condensed polycyclic aromatic hydrocarbons, Tetrahedron 24 (1968), 2505-2516.
A. T. Balaban and Paul von R. Schleyer, "Graph theoretical enumeration of polymantanes", Tetrahedron, (1978), vol. 34, 3599-3609
M. Gardner, Polyhexes and Polyaboloes. Ch. 11 in Mathematical Magic Show. New York: Vintage, pp. 146-159, 1978.
M. Gardner, Tiling with Polyominoes, Polyiamonds and Polyhexes. Chap. 14 in Time Travel and Other Mathematical Bewilderments. New York: W. H. Freeman, pp. 175-187, 1988.
J. V. Knop et al., On the total number of polyhexes, Match, No. 16 (1984), 119-134.
W. F. Lunnon, Counting hexagonal and triangular polyominoes, pp. 87-100 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
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 and Robert A. Russell, Table of n, a(n) for n = 1..36
Frédéric Chyzak, Ivan Gutman, and Peter Paule, Predicting the number of hexagonal systems with 24 and 25 hexagons, Communications in Mathematical and Computer Chemistry (1999) No. 40, 139-151. See p. 141.
A. Clarke, Polyhexes
F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.
D. Gouyou-Beauchamps and P. Leroux, Enumeration of symmetry classes of convex polyominoes on the honeycomb lattice, arXiv:math/0403168 [math.CO], 2004.
M. Keller, Counting polyforms
D. A. Klarner, Cell growth problems, Canad. J. Math. 19 (1967) 851-863.
J. V. Knop, K. Szymanski, Ž. Jeričević, and N. Trinajstić, On the total number of polyhexes, Match, No. 16 (1984), 119-134.
Greg Malen, Érika Roldán, and Rosemberg Toalá-Enríquez, Extremal {p, q}-Animals, Ann. Comb. (2023), p. 3.
John Mason, Counting polyhexes of size 36, updated Oct 27 2023.
Joseph Myers, Polyomino, polyhex and polyiamond tiling
Ed Pegg, Jr., Illustrations of polyforms
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
N. J. A. Sloane, Illustration of initial terms
N. Trinajstich, Z. Jerievi, J. V. Knop, W. R. Muller and K. Szymanski, Computer Generation of Isomeric Structures, Pure & Appl. Chem., Vol. 55, No. 2, pp. 379-390, 1983.
Eric Weisstein's World of Mathematics, Polyhex.

Equals (A006535 + A030225)/2.
Cf. A036359, A002216, A005963, A000228, A001998, A018190.
Cf. A001207, A057973, A364306.
Cf. also A000105, A000577, A103465, A057779, A258206, A258019.

a(13) from Achim Flammenkamp, Feb 15 1999
a(14) from Brendan Owen, Dec 31 2001
a(15) from Joseph Myers, May 05 2002
a(16)-a(20) from Joseph Myers, Sep 21 2002
a(21) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 05 2007
a(22)-a(30) from John Mason, Jul 18 2023

A018190 Number of planar simply-connected polyhexes (or benzenoid hydrocarbons) with n hexagons.

Original entry on oeis.org

1, 1, 3, 7, 22, 81, 331, 1435, 6505, 30086, 141229, 669584, 3198256, 15367577, 74207910, 359863778, 1751594643, 8553649747, 41892642772, 205714411986, 1012565172403, 4994807695197, 24687124900540, 122238208783203

Offset: 1

N. J. A. Sloane, Viviane Rochon (viviane(AT)crt.umontreal.ca), Gilles Caporossi (gillesc(AT)crt.umontreal.ca)

J. Brunvoll, B. N. Cyvin, and S. J. Cyvin, Studies of some chemically relevant polygonal systems: mono-q-polyhexes, ACH Models in Chem., 133 (3) (1996), 277-298.

N. J. A. Sloane, Table of n, a(n) for n = 1..35 [from Vöge et al.]
Gunnar Brinkmann, Gilles Caporossi and Pierre Hansen, A constructive enumeration of fusenes and benzenoids, Journal of Algorithms 45 (2002), pp. 155-166.
Gunnar Brinkmann, Gilles Caporossi and Pierre Hansen, A Survey and New Results on Computer Enumeration of Polyhex and Fusene Hydrocarbons, J. Chem. Inf. Comput. Sci., vol. 43 (2003) 842-851.
G. Caporossi, P. Hansen, Enumeration of Polyhex Hydrocarbons to h = 21, J. Chem. inf. Comput. Sci. 38 (4) (1998) 610-619, Table 1.
James Chapman, Judith Foos, Andrew Nelson, Elizabeth J. Hartung, and Aaron Williams, Pairwise disagreements of Kekulé, Clar, and Fries numbers for benzenoids: a mathematical and computational investigation, arXiv:1804.06071 [math.PR], 2018.
Frédéric Chyzak, Ivan Gutman, and Peter Paule, Predicting the number of hexagonal systems with 24 and 25 hexagons, Communications in Mathematical and Computer Chemistry (1999) No. 40, 139-151. See p. 141.
J. L. Faulon, D. Visco, Jr., and D. Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.
J. V. Knop, W. R. Müller, K. Szymanski, and N. Trinajstić, Use of small computers for large computations: enumeration of polyhex hydrocarbons, J. Chem. Inf. Comput. Sci., 30 (1990), 159-160.
J. V. Knop, K. Szymanski, Ž. Jeričević, and N. Trinajstić, On the total number of polyhexes, Match, No. 16 (1984), 119-134.
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.
Lucia Moura and Ivan Stojmenovic, Backtracking and Isomorph-Free Generation of Polyhexes, Table 2.1 on p. 50 of Handbook of Applied Algorithms (2008). Note a(8) is given as 1453!
S. Nikolić, N. Trinajstić, J. V. Knop, W. R. Müller, On the concept of the weighted spanning tree of dualist, J. Math. Chem. 4 (1990), 357-375.
R. Tošić, D. Mašulović, I. Stojmenović, J. Brunvoll, B. N. Cyvin, and S. J. Cyvin, Enumeration of polyhex hydrocarbons to h = 17, J. Chem. Inf. Comput. Sci., 1995, 35, 181-187.
N. Trinajstić, Z. Jerievi, J. V. Knop, W. R. Müller, and K. Szymanski, Computer Generation of Isomeric Structures, Pure & Appl. Chem., Vol. 55, No. 2, pp. 379-390, 1983.
Markus Vöge, Anthony J. Guttmann, and Iwan Jensen, On the Number of Benzenoid Hydrocarbons, Journal of Chemical Information and Computer Sciences, 42(3) (2002), 456-466.
Eric Weisstein's World of Mathematics, Polyhex.
Eric Weisstein's World of Mathematics, Benzenoid
Eric Weisstein's World of Mathematics, Fusene [That page refers to this sequence as "[simply-connected] catafusenes", but in fact the polyhexes counted by this sequence are not necessarily catacondensed (i.e. tree-like). - _Andrey Zabolotskiy_, Apr 11 2025]

Cf. A000228, A002216, A018190, A038142-A038147.

More terms from Joseph Myers, Nov 06 2003

Further terms added by N. J. A. Sloane from Brinkmann et al. (2003). Jun 04 2005

A001998 Bending a piece of wire of length n+1; walks of length n+1 on a tetrahedron; also non-branched catafusenes with n+2 condensed hexagons.

Original entry on oeis.org

1, 2, 4, 10, 25, 70, 196, 574, 1681, 5002, 14884, 44530, 133225, 399310, 1196836, 3589414, 10764961, 32291602, 96864964, 290585050, 871725625, 2615147350, 7845353476, 23535971854, 70607649841, 211822683802, 635467254244, 1906400965570, 5719200505225, 17157599124190

Offset: 0

N. J. A. Sloane

The wire stays in the plane, there are n bends, each is R,L or O; turning the wire over does not count as a new figure.
Equivalently, walks of n+1 steps on a tetrahedron, visiting n+2 vertices, with n "corners"; the symmetry group is S4, reversing a walk does not count as different. Simply interpret R,L,O as instructions to turn R, turn L, or retrace the last step. Walks are not self-avoiding.
Also, it appears that a(n) gives the number of equivalence classes of n-tuples of 0, 1 and 2, where two n-tuples are equivalent if one can be obtained from the other by a sequence of operations R and C, where R denotes reversal and C denotes taking the 2's complement (C(x)=2-x). This has been verified up to a(19)=290585050. Example: for n=3 there are ten equivalence classes {000, 222}, {001, 100, 122, 221}, {002, 022, 200, 220}, {010, 212}, {011, 110, 112, 211}, {012, 210}, {020, 202}, {021, 102, 120, 201}, {101, 121}, {111}, so a(3)=10. - John W. Layman, Oct 13 2009
There exists a bijection between chains of n+2 hexagons and the above described equivalence classes of n-tuples of 0,1, and 2. Namely, for a given chain of n+2 hexagons we take the sequence of the numbers of vertices of degree 2 (0, 1, or 2) between the consecutive contact vertices on one side of the chain; switching to the other side we obtain the 2's complement of this sequence; reversing the order of the hexagons, we obtain the reverse sequence. The inverse mapping is straightforward. For example, to a linear chain of 7 hexagons there corresponds the 5-tuple 11111. - Emeric Deutsch, Apr 22 2013
If we treat two wire bends (or walks, or tuples) related by turning over (or reversing) as different in any of the above-given interpretations of this sequence, we get A007051 (or A124302). Also, a(n-1) is the sum of first 3 terms in n-th row of A284949, see crossrefs therein. - Andrey Zabolotskiy, Sep 29 2017
a(n-1) is the number of color patterns (set partitions) in an unoriented row of length n using 3 or fewer colors (subsets). - Robert A. Russell, Oct 28 2018
From Allan Bickle, Jun 02 2022: (Start)
a(n) is the number of (unlabeled) 3-paths with n+6 vertices. (A 3-path with order n at least 5 can be constructed from a 4-clique by iteratively adding a new 3-leaf (vertex of degree 3) adjacent to an existing 3-clique containing an existing 3-leaf.)
Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)
a(n) is also the number of distinct planar embeddings of the (n+1)-alkane graph (up to at least n=9, and likely for all n). - Eric W. Weisstein, May 21 2024

			There are 2 ways to bend a piece of wire of length 2 (bend it or not).
For n=4 and a(n-1)=10, the 6 achiral patterns are AAAA, AABB, ABAB, ABBA, ABCA, and ABBC.  The 4 chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB. - _Robert A. Russell_, Oct 28 2018

A. T. Balaban, Enumeration of Cyclic Graphs, pp. 63-105 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976; see p. 75.
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Enumeration of tree-like octagonal systems: catapolyoctagons, ACH Models in Chem. 134 (1997), 55-70.
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2.]
R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 25-61 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [I think this reference does not mention this sequence. - N. J. A. Sloane, Aug 10 2006]
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).

Indranil Ghosh, Table of n, a(n) for n = 0..2092 (terms 0..500 from T. D. Noe)
A. T. Balaban, J. Brunvoll, B. N. Cyvin, and S. J. Cyvin, Enumeration of branched catacondensed benzenoid hydrocarbons and their numbers of Kekulé structures, Tetrahedron 44(1) (1988), 221-228. See Eq. (6), p. 223.
A. T. Balaban and F. Harary, Chemical graphs V: enumeration and proposed nomenclature of benzenoid cata-condensed polycyclic aromatic hydrocarbons, Tetrahedron 24 (1968), 2505-2516.
Christian Barrientos and Sarah Minion, On the Graceful Cartesian Product of Alpha-Trees, Theory and Applications of Graphs, Vol. 4: Iss. 1, Article 3, 2017. (It mentions this sequence on p. 7.)
L. W. Beineke and R. E. Pippert, On the enumeration of planar trees of hexagons, Glasgow Math. J., 15 (1974), 131-147.
L. W. Beineke and R. E. Pippert, On the enumeration of planar trees of hexagons, Glasgow Math. J., 15 (1974), 131-147 [annotated scanned copy].
Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Isomer enumeration of some polygonal systems representing polycyclic conjugated hydrocarbons, Journal of Molecular structure 376 (Issues 1-3) (1996), 495-505. See Table 2 on p. 501.
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Unbranched catacondensed polygonal systems containing hexagons and tetragons, Croatica Chem. Acta, 69 (1996), 757-774.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
R. M. Foster, Solution to Problem E185, Amer. Math. Monthly, 44 (1937), 50-51.
R. M. Foster, Solution to Problem E185, Amer. Math. Monthly, 44 (1937), 50-51 [annotated scanned copy].
F. Harary and R. W. Robinson, Tapeworms, Unpublished manuscript, circa 1973. (Annotated scanned copy)
Thomas M. Liggett and Wenpin Tang, One-dependent hard-core processes and colorings of the star graph, arXiv:1804.06877 [math.PR], 2018.
L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Gyula Tasi and Fujio Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see p. 60).
Eric Weisstein's World of Mathematics, Alkane Graph.
Eric Weisstein's World of Mathematics, Planar Embedding.
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (4,0,-12,9).

Cf. A036359, A002216, A005963, A000228, A001997, A001444, A038766, A007051.
Column 3 of A320750, offset by one. Column k = 0 of A323942, offset by two.
Cf. A124302 (oriented), A107767 (chiral), A182522 (achiral), with varying offsets.
Column 3 of A320750.
The numbers of unlabeled k-paths for k = 2..7 are given in A005418, A001998, A056323, A056324, A056325, and A345207, respectively.
The sequences above converge to A103293(n+1).

a:=[];; for n in [2..45] do if n mod 2 =0 then Add(a,((3^((n-2)/2)+1)/2)^2); else Add(a,  3^((n-3)/2)+(1/4)*(3^(n-2)+1)); fi; od; a; # Muniru A Asiru, Oct 28 2018

A001998 := proc(n) if n = 0 then 1 elif n mod 2 = 1 then (1/4)*(3^n+4*3^((n-1)/2)+1) else (1/4)*(3^n+2*3^(n/2)+1); fi; end;
A001998:=(-1+3*z+2*z**2-8*z**3+3*z**4)/(z-1)/(3*z-1)/(3*z**2-1); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence with an extra leading 1

a[n_?OddQ] := (1/4)*(3^n + 4*3^((n - 1)/2) + 1); a[n_?EvenQ] := (1/4)*(3^n + 2*3^(n/2) + 1); Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Jan 25 2013, from formula *)
LinearRecurrence[{4,0,-12,9},{1,2,4,10},30] (* Harvey P. Dale, Apr 10 2013 *)
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
k=3; Table[Sum[StirlingS2[n,j]+Ach[n,j],{j,k}]/2,{n,40}] (* Robert A. Russell, Oct 28 2018 *)

Vec((1-2*x-4*x^2+6*x^3)/((1-x)*(1-3*x)*(1-3*x^2)) + O(x^50)) \\ Colin Barker, May 15 2016

a(n) = if n mod 2 = 0 then ((3^((n-2)/2)+1)/2)^2 else 3^((n-3)/2)+(1/4)*(3^(n-2)+1).
G.f.: (1-2*x-4*x^2+6*x^3) / ((1-x)*(1-3*x)*(1-3*x^2)). - Corrected by Colin Barker, May 15 2016
a(n) = 4*a(n-1)-12*a(n-3)+9*a(n-4), with a(0)=1, a(1)=2, a(2)=4, a(3)=10. - Harvey P. Dale, Apr 10 2013
a(n) = (1+3^n+3^(1/2*(-1+n))*(2-2*(-1)^n+sqrt(3)+(-1)^n*sqrt(3)))/4. - Colin Barker, May 15 2016
E.g.f.: (2*sqrt(3)*sinh(sqrt(3)*x) + 3*exp(2*x)*cosh(x) + 3*cosh(sqrt(3)*x))/6. - Ilya Gutkovskiy, May 15 2016
From Robert A. Russell, Oct 28 2018: (Start)
a(n-1) = (A124302(n) + A182522(n)) / 2 = A124302(n) - A107767(n-1) = A107767(n-1) + A182522(n).
a(n-1) = Sum_{j=1..k} (S2(n,j) + Ach(n,j)) / 2, where k=3 is the maximum number of colors, S2 is the Stirling subset number A008277, and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).
a(n-1) = A057427(n) + A056326(n) + A056327(n). (End)
a(2*n) = A007051(n)^2; a(2*n+1) = A007051(n)*A007051(n+1). - Todd Simpson, Mar 25 2024

Offset and Maple code corrected by Colin Mallows, Nov 12 1999

Term added by Robert A. Russell, Oct 30 2018

Number of cata-condensed benzenoid hydrocarbons with n hexagons.

Planar cata-polyhexes enumerated by a(n) are the n-celled (planar) polyhexes with perimeter 4n+2, which is the maximal perimeter of an n-celled polyhex. These are such polyhexes that have a tree as their connectedness graph (vertices of this graph correspond to cells and two vertices are connected if the corresponding cells have a common edge). - Tanya Khovanova, Jul 27 2007

Kurz proved the polyomino equivalent of this conjecture as A122133 and abstracts: "In this article we prove a conjecture of Bezdek, Brass and Harborth concerning the maximum volume of the convex hull of any facet-to-facet connected system of n unit hypercubes in the d-dimensional Euclidean space. For d=2 we enumerate the extremal polyominoes and determine the set of possible areas of the convex hull for each n."

cp's OEIS Frontend

A002212 Number of restricted hexagonal polyominoes with n cells.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

PARI

PARI

Sage

Formula

A000228 Number of hexagonal polyominoes (or hexagonal polyforms, or planar polyhexes) with n cells.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A018190 Number of planar simply-connected polyhexes (or benzenoid hydrocarbons) with n hexagons.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A001998 Bending a piece of wire of length n+1; walks of length n+1 on a tetrahedron; also non-branched catafusenes with n+2 condensed hexagons.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

Extensions

A038142 Number of planar cata-polyhexes with n cells.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A005963 Number of restricted hexagonal polyominoes with n cells.

Views

Author

Keywords

References

Crossrefs

A036359 Number of branched catafusenes with n condensed hexagons.

Views

Author

Keywords

References

Crossrefs

Formula

Extensions

A038143 Hexagonal cata-condensed helicenes with n cells (non-planar cata-fused benzenoid hydrocarbons).

Views