|
|
A004149
|
|
Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=2..n-1} a(k)a(n-1-k).
(Formerly M1131)
|
|
15
|
|
|
1, 1, 1, 1, 2, 4, 8, 16, 33, 69, 146, 312, 673, 1463, 3202, 7050, 15605, 34705, 77511, 173779, 390966, 882376, 1997211, 4532593, 10311720, 23512376, 53724350, 122995968, 282096693, 648097855, 1491322824, 3436755328, 7931085771
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Number of Motzkin paths of length n-1 (n>=1) with no peaks and no valleys, i.e., no UD's and no DU's, where U=(1,1) and D=(1,-1). Example: a(7)=16 because there are 17 peakless Motzkin paths of length 6 (see A004148) of which only UHDUHD has a valley (here H=(1,0)). - Emeric Deutsch, Jan 08 2004
a(n+2) = number of Motzkin n-paths that avoid both UU and DD = number of Motzkin n-paths that avoid both UU and UFU. Example: a(7)=16 since of the 21 Motzkin 5-paths, only FUUDD, UFUDD, UUDDF, UUDFD, UUFDD contain a UU or DD (or both). Likewise, only FUUDD, UFUDD, UUDDF, UUDFD, UUFDD contain a UU or UFU. - David Callan, Jul 15 2004
Number of peakless Motzkin paths of length n without UHD's; here U=(1,1), H=(1,0), and D=(1,-1). Example: a(4)=2 because we have HHHH and UHHD.
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210; arXiv:math/0205301 [math.CO], 2002.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science (Sequence 8 mentions a g.f. that gives a sequence that is similar to this sequence but without the first term).
M. S. Waterman, Home Page (contains copies of his papers)
|
|
FORMULA
|
G.f.: 2/(1 - z + z^2 + z^3 + sqrt((1-z^4)(1-2z-z^2))). - Emeric Deutsch, Jan 08 2004
G.f.: 1/(1-x-x^4/(1-x-x^2-x^3-x^4/(1-x-x^2-x^3-x^4/(1-... (continued fraction). - Paul Barry, May 22 2009
D-finite with recurrence: (n+2)*a(n) = (2*n+1)*a(n-1) + (n-1)*a(n-2) + (n-4)*a(n-4) - (2*n-11)*a(n-5) - (n-7)*a(n-6). - Vaclav Kotesovec, Aug 10 2013
G.f. g(x) satisfies x^2*g^2 - (1-x+x^2+x^3)*g + 1 = 0 and
(x^4-1)*(x^2+2*x-1)*x*g'(x) - (x^3-x+2)*(x^3+x^2+x-1)*g(x) + 4*x^3+2*x^2-2 = 0. - Robert Israel, May 07 2015
0 = a(n)*(+a(n+1) + 5*a(n+2) - 4*a(n+3) - 7*a(n+5) - 17*a(n+6) + 10*a(n+7)) + a(n+1)*(-a(n+1) + 6*a(n+2) - 5*a(n+3) + 5*a(n+4) + 2*a(n+5) - 36*a(n+6) + 17*a(n+7)) + a(n+2)*(+a(n+2) + a(n+3) + 7*a(n+4) + 24*a(n+5) - 2*a(n+6) - 7*a(n+7)) + a(n+3)*(-2*a(n+4) - 7*a(n+5) + 5*a(n+6)) + a(n+4)*(+a(n+5) + 5*a(n+6) - 4*a(n+7)) + a(n+5)*(-a(n+5) + 6*a(n+6) - 5*a(n+7)) + a(n+6)*(+a(n+6) + a(n+7)) for all n>=0. - Michael Somos, Jan 09 2017
G.f.: 1/G(x), with G(x)=1-(x-x^3)/(1-x^2/G(x)) (continued fraction). - Nikolaos Pantelidis, Jan 11 2023
|
|
EXAMPLE
|
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 4*x^5 + 8*x^6 + 16*x^7 + 33*x^8 + 69*x^9 + ...
|
|
MAPLE
|
For Maple code producing the g.f. see A004148.
# Alternative:
p:= gfun:-rectoproc({(n-1)*a(n)+(2*n+1)*a(n+1)+(-n-2)*a(n+2)+(-5-n)*a(n+4)+(-13-2*n)*a(n+5)+(n+8)*a(n+6), a(0) = 1, a(1) = 1, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 4}, a(n), remember):
|
|
MATHEMATICA
|
a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-2-k ], {k, 2, n-2} ];
CoefficientList[Series[2/(1-x+x^2+x^3+Sqrt[(1-x^4)(1-2x-x^2)]), {x, 0, 40}], x] (* Harvey P. Dale, Aug 09 2017 *)
|
|
PROG
|
(PARI) {a(n) = polcoeff( (1 - x + x^2 + x^3 - sqrt( (1 - x^4) * (1 - 2*x - x^2) + x^3 * O(x^n))) / (2*x^2), n)}; /* Michael Somos, Oct 28 2005 */
(Haskell)
a004149 n = a004149_list !! n
a004149_list = 1 : 1 : 1 : f [1, 1, 1] where
f xs = y : f (y : xs) where
y = head xs + sum (zipWith (*) (init $ init $ tail xs) (reverse xs))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|