A189912 - OEIS

%I #55 May 06 2021 08:10:25

%S 1,2,4,10,25,66,177,484,1339,3742,10538,29866,85087,243478,699324,

%T 2015082,5822619,16865718,48958404,142390542,414837699,1210439958,

%U 3536809521,10347314544,30306977757,88861597426,260798283502,766092871654,2252240916665

%N Extended Motzkin numbers, Sum_{k>=0} C(n,k)C(k), C(k) the extended Catalan number A057977(k).

%C a(n) = Sum_{k=0..n} binomial(n,k)*A057977(k). For comparison:

%C A001006(n) = Sum_{k=0..n} binomial(n,k)*A057977(k)*[k is even],

%C A005717(n) = Sum_{k=0..n} binomial(n,k)*A057977(k)*[k is odd].

%C 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 _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 G. C. Greubel, <a href="/A189912/b189912.txt">Table of n, a(n) for n = 0..1000</a>

%H Per Alexandersson, <a href="https://www.math.upenn.edu/~peal/polynomials/various-research.htm#A189912">Proof of Werner Schulte's formula</a>.

%H 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 Peter Luschny, <a href="/A180000/a180000.pdf">Die schwingende Fakultät und Orbitalsysteme</a>, August 2011.

%H 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 a(n) = Sum_{k=0..n}(n!/(((n-k)!*floor(k/2)!^2)*(floor(k/2)+1)).

%F 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 a(n) ~ 3^(n+1/2) / (2*sqrt(Pi*n)). - _Vaclav Kotesovec_, Mar 20 2014

%F Conjecture: a(n) = Sum_{k=0..floor(n/2)} (n+1-2*k)*A055151(n,k). - _Werner Schulte_, Oct 23 2016

%F a(n) = Sum_{k=0...n} (n+1-2*k)*(n!)/((k!)*(k+1)!*(n-2k)! ). - _Per W. Alexandersson_, May 28 2020

%p A189912 := proc(n) local k;

%p add(n!/(((n-k)!*iquo(k,2)!^2)*(iquo(k,2)+1)),k=0..n) end:

%p 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 := n -> n*M(n-1)+M(n);

%p seq(A189912(i), i=0..28); # _Peter Luschny_, Sep 12 2011

%t 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 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 A057977[n_] :=  Sum[n! (n + 1 - 2 k)/((k + 1)! (k!) (n - 2 k)!), {k, 0, n}] (* _Per W. Alexandersson_, May 28 2020 *)

%o (Sage)

%o @CachedFunction

%o 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 = lambda n: n*M(n-1) + M(n)

%o [A189912(i) for i in (0..28)] # _Peter Luschny_, Oct 22 2012

%o (PARI) a(n) = sum(k=0, n, binomial(n,k)*k!/( (k\2)!^2 * (k\2+1)) );

%o vector(30, n, a(n-1)) \\ _G. C. Greubel_, Jan 24 2017; Mar 28 2020

%Y Cf. A001006, A001700, A005717, A057977, A126120, A138364, A217539, A217540.

%K nonn

%O 0,2

%A _Peter Luschny_, May 01 2011