

A004148


Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=1..n1} a(k)*a(n1k).
(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 peakless 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 n1 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(n2)= number of UUfree Motzkin npaths = number of DUfree Motzkin npaths.  David Callan, Jul 15 2004
a(n) = number of UUfree Motzkin npaths 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 UUfree Motzkin (n1)paths = number of DUfree Motzkin (n1)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 5paths (pyramids denoted by lowercase letters and separated by a vertical bar): uuuuuddddd, UuudduuddD, uudduuuddd, uuuddduudd.  David Callan, Oct 25 2004
From Emeric Deutsch, Jan 08 2006: (Start)
a(n) = number of Motzkin paths of length n1 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 xaxis 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/(1xx^2x^3/(1xx^2x^3/(1... (continued fraction).  Paul Barry, May 20 2009
A Chebyshev transform of the Motzkin numbers A001006: g.f. is the image of (1x(12x3x^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 BonaKnopfmacher 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, 2413, 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

A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137147.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. S. Waterman, Secondary structure of singlestranded nucleic acids, Studies in Foundations and Combinatorics, Vol. 1, pp. 167212, 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.
P. Barry, On a Generalization of the Narayana Triangle, J. Int. Seq. 14 (2011) # 11.4.5
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291306.
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), 1328.
E. Deutsch, L. W. Shapiro, A bijection between ordered trees and 2Motzkin paths and its many consequences, Disc. Math. 256 (2002) 655670.
R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 7590.
T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 6782.
D. Drake, Bijections from Weighted Dyck Paths to Schröder Paths, J. Int. Seq. 13 (2010) # 10.9.2
Eric S. Egge, Kailee Rubin, Snow Leopard Permutations and Their Even and Odd Threads, arXiv:1508.05310 [math.CO], 2015.
S. B. Ekhad, M. Yang, Automated proofs of many conjectured recurrences in the OEIS made by R. J. Mathar, arXiv:1707.04654 (2017)
Ivo L. Hofacker, Christian M. Reidys, and Peter F. Stadler, Symmetric circular matchings and RNA folding. Discr. Math., 312:100112, 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), 951970. See Eq. 22.
ShuChung Liu, Jun Ma, YeongNan Yeh, Dyck Paths with Peak and ValleyAvoiding Sets, Stud. Appl Math. 121 (3) (2008) 263289 [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 480489; DOI 10.1007/9783642334122_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), 261272.
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, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 7986.
M. S. Waterman, Home Page (contains copies of his papers)


FORMULA

a(n+1) = a(n) + a(1)*a(n2) + a(2)*a(n3) + ... + a(n1)*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)*(1C(z/(13*z+z^2))), where C(z)=(1sqrt(14*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  (1xtx)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=ceiling((n+1)/2)..n} (binomial(k, nk)*binomial(k, nk+1)/k) for n >= 1.  Emeric Deutsch, Nov 12 2003 This formula counts (i) disjointdiagonal dissections by number of diagonals, (ii) peakless Motzkin paths by number of up steps, (iii) UUU and DDDfree Dyck paths by number of ascents.  David Callan, Mar 23 2004
a(n) = Sum_{k=0..floor(n/2)} A131198(nk,k).  Philippe Deléham, Nov 06 2007
G.f.: 1/(1x/(1x^2/(1x/(1x^2/(1x/(1x^2/(1x... (continued fraction).  Paul Barry, Dec 08 2008
G.f.: 1/(1x/(1x(x1)x/(1x(x1)x/(1x(x1)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(nk+j+m,nk)*m/(nk+j+m) * C(nk,kj)*C(kj,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/(1x+x^2x^2/(1x+x^2x^2/(1x+x^2x^2/(1x+x^2x^2/(1... (continued fraction).
a(n) = Sum_{k=0..floor(n/2)} (1)^k*C(nk,k)*A001006(n2*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/(1z/(1z/(1z/(...)))) 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(n1) +(1n)*a(n2) +(52n)*a(n3) +(n4)*a(n4)=0.  R. J. Mathar, Dec 01 2011. This recurrence follows from the WilfZeilberger (WZ) proof technique applied to Sum_{k=ceil((n+1)/2)..n} (binomial(k,nk) * binomial(k,nk+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) x1x^2*(1x^l)/(1x); 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[n1]+Sum[a[k]*a[n2k], {k, 1, n2} ]; Array[a[#]&, 20, 0]
CoefficientList[Series[(1x+x^2Sqrt[x^42x^3x^22x+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(nk+j+m, nk)*m/(nk+j+m)*binomial(nk, kj)*binomial(kj, 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+(1x^2)/sqrt((13*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((1x+x^2sqrt(12*xx^22*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). Cf. A046980 (Hankel transf.)
Sequence in context: A199409 A025241 A203019 * A085022 A003426 A179476
Adjacent sequences: A004145 A004146 A004147 * A004149 A004150 A004151


KEYWORD

easy,nonn,nice,changed


AUTHOR

N. J. A. Sloane


STATUS

approved



