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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002212 Number of restricted hexagonal polyominoes with n cells.
(Formerly M2850 N1145)
88
1, 1, 3, 10, 36, 137, 543, 2219, 9285, 39587, 171369, 751236, 3328218, 14878455, 67030785, 304036170, 1387247580, 6363044315, 29323149825, 135700543190, 630375241380, 2938391049395, 13739779184085, 64430797069375 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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

REFERENCES

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

J. Brunvoll et al., Studies of some chemically relevant polygonal systems: mono-q-polyhexes, ACH Models in Chem., 133 (3) (1996), 277-298, Eq 14.

S. J. Cyvin et al., Number of perifusenes with one internal vertex, Rev. Roumaine Chem., 38 (1993), 65-77.

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

LINKS

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

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

R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449 [cs.DM], 2013.

E. Deutsch, E. Munarini, 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.

N. S. S. Gu, N. Y. Li and T. 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, S. Wagner, The height of multiple edge plane trees, arXiv preprint arXiv:1503.04749, 2015

P.-Y. Huang, S.-C. Liu, 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, 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.

Lily L. Liu, Positivity of three-term recurrence sequences, Electronic J. Combinatorics, 17 (2010), #R57.

H. D. Nguyen, D. Taggart, Mining the OEIS: Ten Experimental Conjectures, 2013; http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.391.2522&rep=rep1&type=pdf. Mentions this sequence. - From N. J. A. Sloane, Mar 16 2014

F. Pakovich, 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, 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.

R. C. Read, Letter to N. J. A. Sloane, Feb 12 1971 (includes 40 terms of A002212 and A002216)

E. Rowland, 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.

Y. Sun, Z. Wang, Consecutive pattern avoidances in non-crossing trees, Graph. Combinat. 26 (2010) 815-832, table 1, {uu,ud}

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 Trees, 2013.

Index entries for reversions of series

FORMULA

Also: a(0)=1, for n>0: a(n)=Sum(Sum a(i)a(j-i), (i=0, .., j)), (j=0, .., n-1). G.f.: A(x)=1+xA(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

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))*int(x^(n-1)*sqrt((x-1)*(5-x)),x=1..5). - 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 changing 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

G.f.: Q(0), where Q(k)= 1 + (4*k+1)*x/((1-x)*(k+1) - x*(1-x)*(2*k+2)*(4*k+3)/(x*(8*k+6)+(2*k+3)*(1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013

G.f.: 2 - 2/( G(0) + 1), where G(k)= 1 + 4*x*(4*k+1)/( (4*k+2)*(1-x) - 2*x*(1-x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1-x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 24 2013

G.f.: (1-x - (1-5*x)*G(0))/(2*x), where G(k)= 1 + 4*x*(4*k+1)/( (4*k+2)*(1-x) - 2*x*(1-x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1-x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 25 2013

a(n) = GegenbauerC(n-1, -n, -3/2)/n for n>=1. - Peter Luschny, May 09 2016

EXAMPLE

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

MAPLE

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

MATHEMATICA

InverseSeries[Series[(y)/(1+3*y+y^2), {y, 0, 24}], x] (* then A(x)=1+y(x) *) (* Len Smiley, Apr 14 2000 *)

(* faster *)

Clear[a];

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

Clear[s];

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

PROG

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

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

(Maxima) 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 */

(Sage)

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

[a.next() for i in range(24)]  # Peter Luschny, Oct 12 2013

(MAGMA) 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

CROSSREFS

Cf. A025238, A000108, A001006, A007317, A026376, A026375.

First differences of A007317.

Row sums of triangle A104259.

Sequence in context: A136576 A129156 A171753 * A149041 A202834 A129247

Adjacent sequences:  A002209 A002210 A002211 * A002213 A002214 A002215

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane, R. C. Read (rcread(AT)math.uwaterloo.ca)

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified August 28 16:15 EDT 2016. Contains 275936 sequences.