%I A004148 M1141
%S A004148 1,1,1,2,4,8,17,37,82,185,423,978,2283,5373,12735,30372,72832,175502,
%T A004148 424748,1032004,2516347,6155441,15101701,37150472,91618049,226460893,
%U A004148 560954047,1392251012,3461824644,8622571758,21511212261,53745962199
%N A004148 Generalized Catalan numbers: a(n+1)=a(n)+ Sum a(k)a(n-1-k), k=1..n-1.
%C A004148 Arises in enumerating secondary structures of RNA molecules. The 17 structures
with 6 nucleotides are shown in the illustration (after Waterman,
1978).
%C A004148 Hankel transform is period 8 sequence [1,1,1,0,-1,-1,-1,0,...].
%C A004148 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 (deutsch(AT)duke.poly.edu),
Nov 19 2003
%C A004148 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 (deutsch(AT)duke.poly.edu),
Nov 19 2003
%C A004148 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 (callan(AT)stat.wisc.edu),
Mar 23 2004
%C A004148 For n>=2, a(n-2)= number of UU-free Motzkin n-paths = number of DU-free
Motzkin n-paths. - David Callan (callan(AT)stat.wisc.edu), Jul 15
2004
%C A004148 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 (callan(AT)stat.wisc.edu), Jul 15 2004
%C A004148 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 (callan(AT)stat.wisc.edu),
Oct 24 2004
%C A004148 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 (callan(AT)stat.wisc.edu),
Oct 25 2004
%C A004148 Comments from Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 08 2006:
"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).
%C A004148 "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).
%C A004148 "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).
%C A004148 "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).
%C A004148 "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.
%C A004148 "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."
%C A004148 a(n+1)= [1, 1, 2, 4, 8, 17, 37,...] gives the antidiagonal sums of triangle
of Narayana A001263 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr),
Oct 21 2006
%C A004148 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 (callan(AT)stat.wisc.edu), May 08 2007
%C A004148 a(n) is also the number of Dyck paths of length n without height of peaks
and valleys 2(mod 3). [From Majun (majun(AT)math.sinica.edu.tw),
Nov 29 2008]
%C A004148 G.f. of a(n+1) is 1/(1-x-x^2-x^3/(1-x-x^2-x^3/(1-... (continued fraction).
[From Paul Barry (pbarry(AT)wit.ie), May 20 2009]
%D A004148 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.
%D A004148 C. Coker, Enumerating a class of lattice paths, Discrete Math., 271,
2003, 13-28.
%D A004148 E. Deutsch and L.W. Shapiro, A bijection between ordered trees and 2-Motzkin
paths and its many consequences, Discrete Math., 256, 2002, 655-670.
%D A004148 R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin.
Theory, Series B, 29 (1980), 75-90.
%D A004148 T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary
structures, Discr. Math., 285 (2004), 67-82.
%D A004148 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]
%D A004148 A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series
in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.
%D A004148 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A004148 P. R. Stein and M. S. Waterman, On some new sequences generalizing the
Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.
%D A004148 M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux et problemes
d'enumeration en bilogie moleculaire, Publ. I.R.M.A. Strasbourg,
1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
%D A004148 M. S. Waterman, Secondary structure of single-stranded nucleic acids,
Studies in Foundations and Combinatorics, Vol. 1, pp. 167-212, 1978.
%H A004148 T. D. Noe, <a href="b004148.txt">Table of n, a(n) for n=0..200</a>
%H A004148 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=421">
Encyclopedia of Combinatorial Structures 421</a>
%H A004148 E. Munarini and N. Z. Salvi, <a href="http://www.mat.univie.ac.at/~slc/
opapers/s49zagaglia.html">Binary strings without zigzags</a>
%H A004148 N. J. A. Sloane, <a href="a4148.gif">Illustration of a(6) = 17</a> (after
Waterman, 1978).
%H A004148 M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.mat.univie.ac.at/
~slc/opapers/s08viennot.html">Polynomes orthogonaux at problemes
d'enumeration en biologie moleculaire</a>, Sem. Loth. Comb. B08l
(1984) 79-86.
%H A004148 M. S. Waterman, <a href="http://www.cmb.usc.edu/people/msw/Waterman.html">
Home Page</a> (contains copies of his papers)
%F A004148 a(n+1)=a(n)+a(1)a(n-2)+a(2)a(n-3)+...+a(n-1)a(0).
%F A004148 G.f.: (1-x+x^2-sqrt(1-2x-x^2-2*x^3+x^4))/(2x^2).
%F A004148 G.f.: (1/z)[1-C(-z/(1-3z+z^2))], where C(z)=(1-sqrt(1-4z))/(2z) is the
Catalan function. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov
19 2003
%F A004148 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 (deutsch(AT)duke.poly.edu),
Nov 19 2003
%F A004148 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
%F A004148 Series reversion of g.f. A(x) is -A(-x) (if offset 1). - Michael Somos,
Jul 20 2003
%F A004148 a(n)=A088518(2n)+A088518(2n+1)-A088518(2n+2). - Emeric Deutsch (deutsch(AT)duke.poly.edu),
Nov 19 2003
%F A004148 a(n)=sum(binomial(k, n-k)*binomial(k, n-k+1)/k, k=ceil((n+1)/2)..n) for
n>=1. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 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 (callan(AT)stat.wisc.edu),
Mar 23 2004
%F A004148 a(n) = Sum_{k, 0<=k<=[n/2]}A131198(n-k,k). - Philippe DELEHAM (kolotoko(AT)wanadoo.fr),
Nov 06 2007
%F A004148 G.f.: 1/(1-x/(1-x^2/(1-x/(1-x^2/(1-x/(1-x^2/(1-x..... (continued fraction).
[From Paul Barry (pbarry(AT)wit.ie), Dec 08 2008]
%F A004148 G.f.: 1/(1-x/(1-x(x-1)-x/(1-x(x-1)-x/(1-x(x-1)-x/(1-... (continued fraction).
[From Paul Barry (pbarry(AT)wit.ie), May 16 2009]
%F A004148 Contribution from Paul D. Hanna (pauldhanna(AT)juno.com), Jun 26 2009:
(Start)
%F A004148 Let A(x)^m = Sum_{n>=0} a(n,m)*x^n, then
%F A004148 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).
%F A004148 (End)
%p A004148 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.
%t A004148 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 ]
%o A004148 (PARI) a(n)=polcoeff((1-x+x^2-sqrt(1-2*x-x^2+x^3*(-2+x+O(x^n))))/2,n+2)
%o A004148 (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)))} [From Paul D. Hanna (pauldhanna(AT)juno.com),
Jun 26 2009]
%Y A004148 Second row of A064645.
%Y A004148 Cf. A088518.
%Y A004148 Sequence in context: A136671 A024557 A025241 this_sequence A085022 A003426
A087803
%Y A004148 Adjacent sequences: A004145 A004146 A004147 this_sequence A004149 A004150
A004151
%K A004148 easy,nonn,nice
%O A004148 0,4
%A A004148 N. J. A. Sloane (njas(AT)research.att.com).
|
