|
| |
|
|
A004148
|
|
Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=1..n-1} a(k)*a(n-1-k).
(Formerly M1141)
|
|
184
|
|
|
|
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, 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
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.)
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
|
|
|
REFERENCES
|
Cameron, Naiomi, and Everett Sullivan. "Peakless Motzkin paths with marked level steps at fixed height." Discrete Mathematics 344.1 (2021): 112154.
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
|
Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger, Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects, in International Conference on Language and Automata Theory and Applications, S. Klein, C. Martín-Vide, D. Shapira (eds), Springer, Cham, pp 195-206, 2018.
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
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) = 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
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
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)
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
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
|
|
|
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 + ...
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
|
|
|
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,
|
|
|
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 *)
|
|
|
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, 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 */
(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)
(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 */
(Magma) R<x>:=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
(Sage)
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()
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn,nice,changed
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
