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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004148 Generalized Catalan numbers: a(n+1) = a(n)+ Sum(k=1..n-1, a(k)*a(n-1-k) ).
(Formerly M1141)
172
1, 1, 1, 2, 4, 8, 17, 37, 82, 185, 423, 978, 2283, 5373, 12735, 30372, 72832, 175502, 424748, 1032004, 2516347, 6155441, 15101701, 37150472, 91618049, 226460893, 560954047, 1392251012, 3461824644, 8622571758, 21511212261, 53745962199, 134474581374 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Arises in enumerating secondary structures of RNA molecules. The 17 structures with 6 nucleotides are shown in the illustration (after Waterman, 1978).

Hankel transform is period 8 sequence [1,1,1,0,-1,-1,-1,0,...].

Enumerates peak-less Motzkin paths of length n. Example: a(5)=8 because we have HHHHH, HHUHD, HUHDH, HUHHD, UHDHH, UHHDH, UHHHD, UUHDD, where U=(1,1), D=(1,-1) and H=(1,0). - Emeric Deutsch, Nov 19 2003

Number of Dyck paths of semilength n-1 with no UUU's and no DDD's, where U=(1,1) and D=(1,-1) (n>0) - Emeric Deutsch, Nov 19 2003

For n>=1, a(n) = number of dissections of an (n+2)-gon with strictly disjoint diagonals and no diagonal incident with the base. (One side of the (n+2)-gon is designated the base.) - David Callan, Mar 23 2004

For n>=2, a(n-2)= number of UU-free Motzkin n-paths = number of DU-free Motzkin n-paths. - David Callan, Jul 15 2004

a(n) = number of UU-free Motzkin n-paths containing no low peaks (A low peak is a UD pair at ground level, i.e. whose removal would create a pair of Motzkin paths). For n>=1, a(n)=number of UU-free Motzkin (n-1)-paths = number of DU-free Motzkin (n-1)-paths. a(n) is asymptotically ~ c n^(-3/2) (1 + phi)^n with c = 1.1043... and phi=(1+sqrt(5))/2. - David Callan, Jul 15 2004. In closed form, c = sqrt(30+14*sqrt(5))/(4*sqrt(Pi)) = 1.104365547309692849... - Vaclav Kotesovec, Sep 11 2013

a(n) = number of Dyck (n+1)-paths with all pyramid sizes >= 2. A pyramid is a maximal subpath of the form k upsteps immediately followed by k downsteps and its size is k. - David Callan, Oct 24 2004

a(n) = number of Dyck paths of semilength n+1 with no small pyramids (n>=1). A pyramid is a maximal sequence of the form k Us followed by k Ds with k>=1. A small pyramid is one with k=1. For example, a[4]=4 counts the following Dyck 5-paths (pyramids denoted by lowercase letters and separated by a vertical bar): uuuuuddddd, Uuudd|uuddD, uudd|uuuddd, uuuddd|uudd. - David Callan, Oct 25 2004

From Emeric Deutsch, Jan 08 2006: (Start)

a(n) = number of Motzkin paths of length n-1 with no peaks at level >=1. Example: a(4)=4 because we have HHH, HUD, UDH and UHD, where U=(1,1), D=(1,-1) and H=(1,0).

a(n) = number of Motzkin paths of length n+1 with no level steps on the x-axis and no peaks at level >=1. Example: a(4)=4 because we have UHHHD, UHDUD, UDUHD and UUHDD, where U=(1,1), D=(1,-1) and H=(1,0).

a(n) = number of Dyck paths of length 2n having no ascents and descents of even length. An ascent (descent) is a maximal sequence of up (down) steps. Example: a(4)=4 because we have UDUDUDUD, UDUUUDDD, UUUDDDUD and UUUDUDDD, where U=(1,1), D=(1,-1) and H=(1,0).

a(n) = number of Dyck paths of length 2n having ascents only of length 1 or 2 and having no peaks of the form UUDD. An ascent is a maximal sequence of up steps. Example: a(4)=4 because we have UDUDUDUD, UDUUDUDD, UUDUDDUD and UUDUDUDD, where U=(1,1), D=(1,-1) and H=(1,0).

a(n) = number of noncrossing partitions of [n+1] having no singletons and in each block the two leftmost points are of the form i,i+1. Example: a(4)=4 because we have 12345, 12/345, 123/45 and 125/34; the noncrossing partition 145/23 does not satisfy the requirements because 1 and 4 are not consecutive.

a(n) = number of noncrossing partitions of [n+1] with no singletons, except possibly the block /1/ and no blocks of the form /i,i+1/, except possibly the block /1,2/. Example: a(4)=4 because we have 12345, 1/2345, 12/345 and 15/234.

(End)

a(n+1)= [1, 1, 2, 4, 8, 17, 37,...] gives the antidiagonal sums of triangle of Narayana A001263 . - Philippe Deléham, Oct 21 2006

a(n) = number of Dyck (n+1)-paths with no UDUs and no DUDs. For example, a(4)=4 counts UUUUUDDDDD, UUUDDUUDDD, UUDDUUUDDD, UUUDDDUUDD. - David Callan, May 08 2007

a(n) is also the number of Dyck paths of semilength n without height of peaks and valleys 2(mod 3). [From Majun (majun(AT)math.sinica.edu.tw), Nov 29 2008]

G.f. of a(n+1) is 1/(1-x-x^2-x^3/(1-x-x^2-x^3/(1-... (continued fraction). - Paul Barry, May 20 2009

A Chebyshev transform of the Motzkin numbers A001006: g.f. is the image of (1-x-(1-2x-3x^2)^(1/2))/(2x^2) under the mapping that takes g(x) to (1/(1+x^2))g(x/(1+x^2)). - Paul Barry, Mar 10 2010

For n>=1, the number of lattice paths of weight n -1 that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: an (1,0)-step with weight 1, an (1,0)-step with weight 2, a (1,1)-step with weight 2, and  a (1,-1)-step with weight 1. The weight of a path is the sum of the weights of its steps. a(4)=4 because, denoting by h (H) the (1,0)-step of weight 1 (2), and u=(1,1), d=(1,-1), we have the following four paths of weight 3: hH, Hh, hhh, and ud. (See the g.f. C(x) on p. 295 of the Bona-Knopfmacher reference).

From David Callan, Aug 27 2014: (Start)

a(n) = number of noncrossing partitions of [n] with all blocks of size 1 or 2 and no blocks of the form /i,i+1/. Example: a(4)=4 because we have 1234, 13/2/4, 14/2/3, and 1/24/3.

It appears that a(n) = number of permutations of [n] that avoid the three dashed patterns 123, 132, 24-13, and contain no small jumps (jumps of one unit). For example, a(4)=4 counts 3214, 3241, 4213, and 4321 but not 4312 because 12 is a small jump. (End)

REFERENCES

Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.

A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. S. Waterman, Secondary structure of single-stranded nucleic acids, Studies in Foundations and Combinatorics, Vol. 1, pp. 167-212, 1978.

LINKS

T. D. Noe and Seiichi Manyama, Table of n, a(n) for n = 0..2404 (first 201 terms from T. D. Noe)

Sergey Avgustinovich, Sergey Kitaev and Alexander Valyuzhenich, Avoidance of boxed mesh patterns on permutations.

M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.

C. Coker, Enumerating a class of lattice paths, Discrete Math., 271 (2003), 13-28.

E. Deutsch, L. W. Shapiro, A bijection between ordered trees and 2-Motzkin paths and its many consequences, Disc. Math. 256 (2002) 655-670.

R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.

T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 67-82.

Eric S. Egge, Kailee Rubin, Snow Leopard Permutations and Their Even and Odd Threads, arXiv:1508.05310 [math.CO], 2015.

Ivo L. Hofacker, Christian M. Reidys, and Peter F. Stadler, Symmetric circular matchings and RNA folding. Discr. Math., 312:100-112, 2012. See Eq. 27.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 421

Emma Y. Jin and Christian M. Reidys, Asymptotic Enumeration of RNA Structures with Pseudoknots, Bulletin of Mathematical Biology 70 (2008), 951-970. See Eq. 22.

Shu-Chung Liu, Jun Ma, Yeong-Nan Yeh, Dyck Paths with Peak- and Valley-Avoiding Sets, Stud. Appl Math. 121 (3) (2008) 263-289 [From Majun (majun(AT)math.sinica.edu.tw), Nov 29 2008]

E. Munarini and N. Z. Salvi, Binary strings without zigzags

A. Nkwanta, A. Tefera, Curious Relations and Identities Involving the Catalan Generating Function and Numbers, Journal of Integer Sequences, 16 (2013), #13.9.5.

A. Panayotopoulos and P. Vlamos, Cutting Degree of Meanders, Artificial Intelligence Applications and Innovations, IFIP Advances in Information and Communication Technology, Volume 382, 2012, pp 480-489; DOI 10.1007/978-3-642-33412-2_49. - From N. J. A. Sloane, Dec 29 2012

N. J. A. Sloane, Illustration of a(6) = 17 (after Waterman, 1978).

P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.

P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers [Corrected annotated scanned copy]

M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86.

M. S. Waterman, Home Page (contains copies of his papers)

FORMULA

a(n+1) = a(n) + a(1)*a(n-2) + a(2)*a(n-3) + ... + a(n-1)*a(0).

G.f.: (1 - x + x^2 - sqrt(1 - 2*x - x^2 - 2*x^3+x^4)) / (2*x^2). - Michael Somos, Jul 20 2003

G.f.: (1/z)*(1-C(-z/(1-3*z+z^2))), where C(z)=(1-sqrt(1-4*z))/(2*z) is the Catalan function. - Emeric Deutsch, Nov 19 2003

G.f.: 1+F(x, x)/x, where F(x, t) is the g.f. of the Narayana numbers: xF^2-(1-x-tx)F+tx=0. - Emeric Deutsch, Nov 19 2003

G.f. A(x) satisfies the functional equation: x^2*A(x)^2 - (x^2 - x + 1)*A(x) + 1 = 0. - Michael Somos, Jul 20 2003

Series reversion of g.f. A(x) is -A(-x) (if offset 1). - Michael Somos, Jul 20 2003

a(n) = A088518(2n)+A088518(2n+1)-A088518(2n+2). - Emeric Deutsch, Nov 19 2003

a(n) = Sum_{k=ceil((n+1)/2)..n} (binomial(k, n-k)*binomial(k, n-k+1)/k) for n>=1. - Emeric Deutsch, Nov 12 2003 This formula counts (i) disjoint-diagonal dissections by number of diagonals, (ii) peak-less Motzkin paths by number of up steps, (iii) UUU- and DDD-free Dyck paths by number of ascents. - David Callan, Mar 23 2004

a(n) = Sum_{k, 0<=k<=[n/2]}A131198(n-k,k). - Philippe Deléham, Nov 06 2007

G.f.: 1/(1-x/(1-x^2/(1-x/(1-x^2/(1-x/(1-x^2/(1-x..... (continued fraction). - Paul Barry, Dec 08 2008

G.f.: 1/(1-x/(1-x(x-1)-x/(1-x(x-1)-x/(1-x(x-1)-x/(1-... (continued fraction). - Paul Barry, May 16 2009

From Paul D. Hanna, Jun 26 2009: (Start)

Let A(x)^m = Sum_{n>=0} a(n,m)*x^n, then

a(n,m) = Sum_{k=0..n} Sum_{j=0..k} C(n-k+j+m,n-k)*m/(n-k+j+m) * C(n-k,k-j)*C(k-j,j).

(End)

From Paul Barry, Mar 10 2010: (Start)

G.f.: (1/(1+x^2))*M(x/(1+x^2)), M(x) the g.f. of the Motzkin numbers A001006;

G.f.: 1/(1-x+x^2-x^2/(1-x+x^2-x^2/(1-x+x^2-x^2/(1-x+x^2-x^2/(1-... (continued fraction).

a(n) = Sum_{k=0..floor(n/2)} (-1)^k*C(n-k,k)*A001006(n-2*k). (End)

G.f.: 1 + x*exp( Sum_{n>=1} (x^n/n)*[Sum_{k=0..n} C(n,k)^2*x^k] ). - Paul D. Hanna, Mar 15 2011

G.f.: exp( Sum_{n>=1} A051292(n)*x^n/n ), where A051292(n) is a Whitney number of level n. - Paul D. Hanna, Mar 15 2011

Let the g.f. be A(x), then B(x)=(1+x*A(x)) = 1/(1-z/(1-z/(1-z/(...)))) where z=x/(1+x+x^2), B(x) = 1 +1*x + 1*x^2 +1*x^3 + 2*x^4 + 4*x^5 +... is the g.f. of this sequence prepended with 1; more generally B(x) = C(x/(1+x+x^2)) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011

Conjecture: (n+2)*a(n) -(2n+1)*a(n-1) +(1-n)*a(n-2) +(5-2n)*a(n-3) +(n-4)*a(n-4)=0. - R. J. Mathar, Dec 01 2011. This recurrence follows from the Wilf-Zeilberger (WZ) proof technique applied to Sum_{k=ceil((n+1)/2)..n} (binomial(k,n-k) * binomial(k,n-k+1)/k). - T. Amdeberhan, Jul 23 2012

Given g.f. A(x), then B(x) = x * A(x) satisfies B(x) = x + x*B(x) / (1 - x*B(x)). - Michael Somos, Jun 05 2014

G.f.: 1 - x / (x^2 - 1 / (1 - x / (x^2 - 1 / (1 - x / (x^2 - ...))))). - Michael Somos, Jun 05 2014

0 = a(n)*(+a(n+1) - 5*a(n+2) - 4*a(n+3) - 11*a(n+4) + 7*a(n+5)) + a(n+1)*(+a(n+1) + 6*a(n+2) + 12*a(n+3) + 11*a(n+4) - 11*a(n+5)) + a(n+2)*(-a(n+2) - 7*a(n+3) + 12*a(n+4) - 4*a(n+5)) + a(n+3)*(-a(n+3) + 6*a(n+4) - 5*a(n+5)) + a(n+4)*(+a(n+4) + a(n+5)) if n>=-1. - Michael Somos, Jun 05 2014

EXAMPLE

G.f. = 1 + x + x^2 + 2*x^3 + 4*x^4 + 8*x^5 + 17*x^6 + 37*x^7 + 82*x^8 + 185*x^9 + 432*x^10 + ...

MAPLE

w:=proc(l) x-1-x^2*(1-x^l)/(1-x); end; S:=proc(l) ( -w(l) - sqrt( w(l)^2 - 4*x^2) )/(2*x^2); end; # S(0) is g.f. for Motzkin numbers A001006, S(1) is g.f. for this sequence, S(2) is g.f. for A004149, etc.

MATHEMATICA

a[0]=1; a[n_Integer] := a[n]=a[n-1]+Sum[a[k]*a[n-2-k], {k, 1, n-2} ]; Array[a[#]&, 20, 0]

CoefficientList[Series[(1-x+x^2-Sqrt[x^4-2x^3-x^2-2x+1])/(2x^2), {x, 0, 60}], x] (* Harvey P. Dale, May 09 2011 *)

a[ n_] := SeriesCoefficient[ (1 - x + x^2 - Sqrt[1 - 2 x - x^2 - 2 x^3 + x^4]) / (2 x^2), {x, 0, n}]; (* Michael Somos, Jun 05 2014 *)

PROG

(PARI) {a(n) = polcoeff( (1 - x + x^2 - sqrt(1 - 2*x - x^2 + x^3 * (-2 + x + O(x^n)))) / 2, n + 2)}; /* Michael Somos, Jul 20 2003 */

(PARI) a(n, m=1)=sum(k=0, n, sum(j=0, k, binomial(n-k+j+m, n-k)*m/(n-k+j+m)*binomial(n-k, k-j)*binomial(k-j, j))) \\ Paul D. Hanna, Jun 26 2009

(PARI) {a(n)=polcoeff(1+x*exp(sum(m=1, n, sum(k=0, m, binomial(m, k)^2*x^k)*x^m/m)+x*O(x^n)), n)} /* Paul D. Hanna */

(PARI) {a(n)=local(A051292=1+(1-x^2)/sqrt((1-3*x+x^2)*(1+x+x^2) +x*O(x^n))); polcoeff(exp(sum(m=1, n, polcoeff(A051292, m)*x^m/m)+x*O(x^n)), n)} /* Paul D. Hanna */

(Maxima) a(n):=coeff(taylor((1-x+x^2-sqrt(1-2*x-x^2-2*x^3+x^4))/(2*x^2), x, 0, n), x, n);

makelist(a(n), n, 0, 12); // Emanuele Munarini, Jul 07 2001

(Haskell)

a004148 n = a004148_list !! n

a004148_list = 1 : f [1] where

f xs'@(x:xs) = y : f (y : xs') where

y = x + sum (zipWith (*) xs $ reverse $ tail xs)

-- Reinhard Zumkeller, Nov 13 2012

(PARI) {a(n) = my(A = 1 + O(x)); for(k=1, n, A = 1 - x / (x^2 - 1/A)); polcoeff( A, n)}; /* Michael Somos, Jun 05 2014 */

CROSSREFS

Second row of A064645.

Cf. A088518, A051292 (lgf).

Sequence in context: A199409 A025241 A203019 * A085022 A003426 A179476

Adjacent sequences:  A004145 A004146 A004147 * A004149 A004150 A004151

KEYWORD

easy,nonn,nice

AUTHOR

N. J. A. Sloane

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 June 27 02:59 EDT 2017. Contains 288777 sequences.