cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A004148 Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=1..n-1} a(k)*a(n-1-k).

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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, 0, -1, -1, -1, 0, 1, 1, ...] (A046980).
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). - 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)
Number of DU_{k}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. - Sergey Kirgizov, Apr 08 2018
a(n) is also the number of 3412-avoiding involutions on [n] with no transpositions of the form (i,i+1). For example, a(4)=4 counts the involutions 1234, 1432, 3214, 4231. - Juan B. Gil, May 23 2020
For n >= 2, a(n) equals the number of Dyck paths with air pockets of length n. A Dyck path with air pockets is a nonempty lattice path in the first quadrant of Z^2 starting at the origin, ending on the x-axis, and consisting of up-steps U = (1,1) and down-steps D_k = (1, -k), k >= 1, where two down-steps cannot be consecutive. For example, the only path of length 2 is UD_1; for length 3 we have UU_D2; for length 4 there are 2 paths: UUUD_3, UD_1UD_1; and for length 5 we have 4 paths: UUUUD_4, UUD_2UD_1, UD_1UUD_2, UUD_1UD_2. - Sergey Kirgizov, Dec 15 2022

Examples

			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 + ...
Det([1]) = 1, Det([1, 1; 1, 1]) = 0, Det([1, 1, 1; 1, 1, 2; 1, 2, 4]) = -1. - _Michael Somos_, May 12 2022

References

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

Links

Crossrefs

Second row of A064645.
Cf. A000108, A001006, A088518, A051292 (lgf), A004149, A131198.
Cf. A046980 (Hankel transform).

Programs

  • 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
  • Magma
    R:=PowerSeriesRing(Rationals(), 35); Coefficients(R!( (1-x+x^2 - Sqrt(1-2*x-x^2-2*x^3+x^4))/(2*x^2) )); // G. C. Greubel, Dec 30 2019
  • 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,n-2}]; Array[a, 35, 0]
CoefficientList[Series[(1-x+x^2-Sqrt[x^4-2x^3-x^2-2x+1])/(2x^2), {x,0,40}], x] (* Harvey P. Dale, May 09 2011 *)
a[n_]:= SeriesCoefficient[(1 -x +x^2 -Sqrt[1 -2x -x^2 -2x^3 +x^4])/(2x^2), {x, 0, n}]; (* Michael Somos, Jun 05 2014 *)
a[n_] := HypergeometricPFQ[{-n/2, (1-n)/2, (1-n)/2, 1-n/2}, {2, -n, -n + 1}, 16]; Array[a, 33, 0] (* Peter Luschny, Jan 25 2020 *)
Table[If[n==0,1, Sum[(Binomial[n-k,k+1]Binomial[n-k,k]/(n-k)), {k,0,n-1}]], {n,0,10}] (* Rigoberto Florez, Apr 17 2023 *)
CoefficientList[Nest[1+x(1-x) #+x^2 #^2 &, 1+O[x], 32], x](* Oliver Seipel, Dec 21 2024 *)
  • 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 */
  • 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, Mar 15 2011 */
  • 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, Mar 15 2011 */
  • 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 */
  • Sage
    def A004148_list(prec):
    P = PowerSeriesRing(ZZ, 'x', prec)
    x = P.gen().O(prec)
    return ( (1-x+x^2 -sqrt(1-2*x-x^2-2*x^3+x^4))/(2*x^2) ).list()
A004148_list(35) # G. C. Greubel, Dec 30 2019

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=ceiling((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..floor(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
D-finite with recurrence: (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=ceiling((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
a(n) = hypergeom([-n/2, (1 - n)/2, (1 - n)/2, 1 - n/2], [2, -n, -n + 1], 16). - Peter Luschny, Jan 25 2020
a(n) = Sum_{k=0..n-1} binomial(n-k,k+1)*binomial(n-k,k)/(n-k) for n > 0. - Rigoberto Florez, Apr 17 2023
a(n) ~ 5^(1/4) * phi^(2*n + 2) / (2 * sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, May 05 2023

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.