cp's OEIS Frontend

A189912 Extended Motzkin numbers, Sum_{k>=0} C(n,k)*C(k), where C(k) is the extended Catalan number A057977(k).

%I A189912 #61 Feb 14 2025 02:56:08
%S A189912 1,2,4,10,25,66,177,484,1339,3742,10538,29866,85087,243478,699324,
%T A189912 2015082,5822619,16865718,48958404,142390542,414837699,1210439958,
%U A189912 3536809521,10347314544,30306977757,88861597426,260798283502,766092871654,2252240916665
%N A189912 Extended Motzkin numbers, Sum_{k>=0} C(n,k)*C(k), where C(k) is the extended Catalan number A057977(k).
%C A189912 a(n) = Sum_{k=0..n} binomial(n,k)*A057977(k). For comparison:
%C A189912 A001006(n) = Sum_{k=0..n} binomial(n,k)*A057977(k)*[k is even],
%C A189912 A005717(n) = Sum_{k=0..n} binomial(n,k)*A057977(k)*[k is odd].
%C A189912 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).
%C 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
%H A189912 G. C. Greubel, <a href="/A189912/b189912.txt">Table of n, a(n) for n = 0..1000</a>
%H A189912 Per Alexandersson, <a href="https://www.math.upenn.edu/~peal/polynomials/various-research.htm#A189912">Proof of Werner Schulte's formula</a>.
%H A189912 A. Asinowski and G. Rote, <a href="http://arxiv.org/abs/1502.04925">Point sets with many non-crossing matchings</a>, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.
%H A189912 Peter Luschny, <a href="/A180000/a180000.pdf">Die schwingende Fakultät und Orbitalsysteme</a>, August 2011.
%H A189912 Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/OddsAndEnds#The_Scambler_statistic_on_Dyck_words">The Scambler_statistic_on_Dyck_words</a>.
%F A189912 a(n) = Sum_{k=0..n} n!/(((n-k)!*floor(k/2)!^2)*(floor(k/2)+1)).
%F A189912 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
%F A189912 a(n) ~ 3^(n+1/2) / (2*sqrt(Pi*n)). - _Vaclav Kotesovec_, Mar 20 2014
%F A189912 Conjecture: a(n) = Sum_{k=0..floor(n/2)} (n+1-2*k)*A055151(n,k). - _Werner Schulte_, Oct 23 2016
%F A189912 a(n) = Sum_{k=0..floor(n/2)} (n+1-2*k)*n!/(k!*(k+1)!*(n-2*k)!). - _Per W. Alexandersson_, May 28 2020
%p A189912 A189912 := proc(n) local k;
%p A189912 add(n!/(((n-k)!*iquo(k,2)!^2)*(iquo(k,2)+1)),k=0..n) end:
%p A189912 M := proc(n) option remember; `if`(n<2, 1, (3*(n-1)*M(n-2)+(2*n+1)*M(n-1))/(n+2)) end:
%p A189912 A189912 := n -> n*M(n-1)+M(n);
%p A189912 seq(A189912(i), i=0..28); # _Peter Luschny_, Sep 12 2011
%t A189912 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_ *)
%t A189912 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 *)
%t A189912 A057977[n_] :=  Sum[n! (n + 1 - 2 k)/((k + 1)! (k!) (n - 2 k)!), {k, 0, n}] (* _Per W. Alexandersson_, May 28 2020 *)
%o A189912 (Sage)
%o A189912 @CachedFunction
%o A189912 def M(n): return (3*(n-1)*M(n-2)+(2*n+1)*M(n-1))/(n+2) if n>1 else 1
%o A189912 A189912 = lambda n: n*M(n-1) + M(n)
%o A189912 [A189912(i) for i in (0..28)] # _Peter Luschny_, Oct 22 2012
%o A189912 (PARI) a(n) = sum(k=0, n, binomial(n,k)*k!/( (k\2)!^2 * (k\2+1)) );
%o A189912 vector(30, n, a(n-1)) \\ _G. C. Greubel_, Jan 24 2017; Mar 28 2020
%Y A189912 Cf. A001006, A001700, A005717, A057977, A126120, A138364, A217539, A217540.
%K A189912 nonn
%O A189912 0,2
%A A189912 _Peter Luschny_, May 01 2011