The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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:
A001006(n) = Sum_{k=0..n} binomial(n,k)*A057977(k)*[k is even],
A005717(n) = Sum_{k=0..n} binomial(n,k)*A057977(k)*[k is odd].
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
A. Asinowski and G. Rote, Point sets with many non-crossing matchings, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.
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
a(n) ~ 3^(n+1/2) / (2*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 20 2014
Conjecture: a(n) = Sum_{k=0..floor(n/2)} (n+1-2*k)*A055151(n,k). - Werner Schulte, Oct 23 2016
a(n) = Sum_{k=0...n} (n+1-2*k)*(n!)/((k!)*(k+1)!*(n-2k)! ). - Per W. Alexandersson, May 28 2020
MAPLE
A189912 := proc(n) local k;
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:
A189912 := n -> n*M(n-1)+M(n);
seq(A189912(i), i=0..28); # Peter Luschny, Sep 12 2011
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 *)
A057977[n_] := Sum[n! (n + 1 - 2 k)/((k + 1)! (k!) (n - 2 k)!), {k, 0, n}] (* Per W. Alexandersson, May 28 2020 *)
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)
[A189912(i) for i in (0..28)] # Peter Luschny, Oct 22 2012
(PARI) a(n) = sum(k=0, n, binomial(n, k)*k!/( (k\2)!^2 * (k\2+1)) );
vector(30, n, a(n-1)) \\ G. C. Greubel, Jan 24 2017; Mar 28 2020
CROSSREFS
Sequence in context: A166516 A230552 A230555 * A268321 A195981 A124500
KEYWORD
nonn
AUTHOR
Peter Luschny, May 01 2011
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 16:32 EDT 2024. Contains 372664 sequences. (Running on oeis4.)