|
|
A189912
|
|
Extended Motzkin numbers, Sum_{k>=0} C(n,k)C(k), C(k) the extended Catalan number A057977(k).
|
|
9
|
|
|
1, 2, 4, 10, 25, 66, 177, 484, 1339, 3742, 10538, 29866, 85087, 243478, 699324, 2015082, 5822619, 16865718, 48958404, 142390542, 414837699, 1210439958, 3536809521, 10347314544, 30306977757, 88861597426, 260798283502, 766092871654, 2252240916665
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
a(n) = Sum_{k=0..n} binomial(n,k)*A057977(k). For comparison:
Thus one might simply say: The extended Motzkin numbers are the binomial sum of the extended Catalan numbers. Moreover: The Catalan numbers aerated with 0's at odd positions (A126120) are the inverse binomial transform of the Motzkin numbers (A001006). The complementary Catalan numbers (A001700) aerated with 0's at even positions (A138364) are the inverse binomial transform of the complementary Motzkin numbers (A005717). The extended Catalan numbers (A057977 = A126120 + A138364) are the inverse binomial transform of the extended Motzkin numbers (A189912).
David Scambler observed that [1, a(n-1)] for n >= 1 count the Dyck paths of semilength n which satisfy the condition "number of peaks <= number of returns + number of hills". - Peter Luschny, Oct 22 2012
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=0..n}(n!/(((n-k)!*floor(k/2)!^2)*(floor(k/2)+1)).
Recurrence: (n+2)*(n^2 + 2*n - 5)*a(n) = (2*n^3 + 7*n^2 - 14*n - 7)*a(n-1) + 3*(n-1)*(n^2 + 4*n - 2)*a(n-2). - Vaclav Kotesovec, Mar 20 2014
|
|
MAPLE
|
add(n!/(((n-k)!*iquo(k, 2)!^2)*(iquo(k, 2)+1)), k=0..n) end:
M := proc(n) option remember; `if`(n<2, 1, (3*(n-1)*M(n-2)+(2*n+1)*M(n-1))/(n+2)) end:
|
|
MATHEMATICA
|
A057977[n_] := n!/(Quotient[n, 2]!^2*(Quotient[n, 2] + 1)); a[n_] := Sum[Binomial[n, k]*A057977[k], {k, 0, n}]; Table[a[n], {n, 0, 28}] (* Jean-François Alcover, May 21 2013, after Peter Luschny *)
Table[Sum[n!/(((n-k)!*Floor[k/2]!^2)*(Floor[k/2]+1)), {k, 0, n}], {n, 0, 30}] (* G. C. Greubel, Jan 24 2017 *)
|
|
PROG
|
(Sage)
@CachedFunction
def M(n): return (3*(n-1)*M(n-2)+(2*n+1)*M(n-1))/(n+2) if n>1 else 1
A189912 = lambda n: n*M(n-1) + M(n)
(PARI) a(n) = sum(k=0, n, binomial(n, k)*k!/( (k\2)!^2 * (k\2+1)) );
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|