A217540 -id:A217540 - 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).

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

Offset: 0

Peter Luschny, May 01 2011

nonn

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

G. C. Greubel, Table of n, a(n) for n = 0..1000
Per Alexandersson, Proof of Werner Schulte's formula.
A. Asinowski and G. Rote, Point sets with many non-crossing matchings, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.
Peter Luschny, Die schwingende Fakultät und Orbitalsysteme, August 2011.
Peter Luschny, The Scambler_statistic_on_Dyck_words.

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

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

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 *)

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

@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

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..floor(n/2)} (n+1-2*k)*n!/(k!*(k+1)!*(n-2*k)!). - Per W. Alexandersson, May 28 2020

A113682 Expansion of 2/(sqrt(1-2x-3x^2)(1+x+sqrt(1-2x-3*x^2))).

Original entry on oeis.org

1, 1, 4, 9, 26, 70, 197, 553, 1570, 4476, 12827, 36894, 106471, 308113, 893804, 2598313, 7567466, 22076404, 64498427, 188689684, 552675365, 1620567763, 4756614062, 13974168190, 41088418151, 120906613075, 356035078102

Offset: 0

Paul Barry, Nov 04 2005

Convolution of A002426 and A005043. Diagonal sums of A094531.
Hankel transform is A164611. - Paul Barry, Aug 17 2009
David Scambler observed that [1,0,a(n-2)] for n>=2 count the Dyck paths of semilength n such that the number of peaks equals the number of hills plus the number of returns. - Peter Luschny, Oct 22 2012
Conjectural congruences (working with an offset of 1): a(n*p^k) == a(n*p^(k-1)) ( mod p^(2*k) ) for prime p >= 5 and positive integers n and k. - Peter Bala, Mar 15 2020

G. C. Greubel, Table of n, a(n) for n = 0..1000
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.

Cf. A002426, A005043, A094531, A217539, A217540, A246437, A005717.

[(Evaluate(GegenbauerPolynomial(n+1, -n-1), -1/2) + (-1)^n)/2: n in [0..40]];  // G. C. Greubel, Apr 04 2024

ex[x_]:=Module[{sx=Sqrt[1-2x-3x^2]},2/(sx (1+x+sx))]; CoefficientList[ Series[ ex[x],{x,0,40}],x] (* Harvey P. Dale, May 28 2012 *)
Flatten[{1, Table[Coefficient[Sum[(1 + x + x^2)^k, {k, 0, n}], x^n], {n, 1, 30}]}] (* Vaclav Kotesovec, Jan 08 2016 *)

makelist((ultraspherical(n+1,-n-1,-1/2)+(-1)^n)/2,n,0,12); /* Emanuele Munarini, Dec 20 2016 */

x='x+O('x^50); Vec(2/(sqrt(1-2*x-3*x^2)*(1+x+sqrt(1-2*x-3*x^2)))) \\ G. C. Greubel, Feb 28 2017

[(gegenbauer(n+1,-n-1,-1/2) +(-1)^n)/2 for n in range(41)] # G. C. Greubel, Apr 04 2024

a(n) = Sum_{k=0..floor(n/2)} ( Sum_{i=0..n-k} C(n-2k-i, i)*C(n-k, k+i) ).
a(n) = Sum_{k=0..n} A002426(k)*A005043(n-k).
a(n) = Sum_{k=0..n} C(n+1,k+1)*C(k,n-k). - Paul Barry, Aug 21 2007
a(n) = (A002426(n+1) + (-1)^n)/2. - Paul Barry, Aug 17 2009
G.f.: d/dx log(1/(1-x*A005043(x))). - Vladimir Kruchinin, Apr 18 2011
D-finite with recurrence: (n+1)*a(n) +(-n-1)*a(n-1) +(-5*n+1)*a(n-2) +3*(-n+1)*a(n-3)=0. - R. J. Mathar, Nov 26 2012
Recurrence: (n+4)*a(n+3)-(n+4)*a(n+2)-(5*n+14)*a(n+1)-3*(n+2)*a(n)=0. Remark: this recurrence can be obtained using the identity a(n) = (t(n+1)+(-1)^n)/2 and the recurrence of the central trinomial coefficients t(n) = A002426(n). So, the above P-finite recurrences are true. - Emanuele Munarini, Dec 20 2016
a(n) = (-1)^(n+1) * (hypergeom([1/2, -n-1], [1], 4) - 1)/2. - Vladimir Reshetnikov, Apr 25 2016
a(n) = (-1)^n + A246437(n+1). - Vladimir Reshetnikov, Apr 25 2016

A217539 Number of Dyck paths of semilength n which satisfy the condition: number of returns + number of hills < number of peaks.

Original entry on oeis.org

0, 0, 0, 1, 4, 17, 66, 252, 946, 3523, 13054, 48248, 178146, 657813, 2430962, 8995521, 33342588, 123822171, 460772982, 1718304786, 6421729878, 24051429321, 90272123682, 339522804129, 1279556832780, 4831639423695, 18278491474726, 69272752632502, 262981858878706

Offset: 0

Peter Luschny, Oct 22 2012

nonn

David Scambler observed that [1, 0, A113682(n-2)] for n>=2 count the Dyck paths of semilength n which satisfy the condition "number of peaks = number of returns + number of hills" and [1, A189912(n-1)] for n>=1 count the paths which satisfy the condition "number of peaks <= number of returns + number of hills".

			a(4) = 4 count the Dyck words
[11010100] (()()()) [11011000] (()(()))
[11100100] ((())()) [11101000] ((()())) .

Cf. A217540.

A217539 := proc(n) local k; if n = 0 then 0 else (2*n)!/(n!^2*(n+1)) - add((n-1)!/(((n-1-k)!*iquo(k,2)!^2)*(iquo(k,2)+1)), k=0..n-1) fi end: seq(A217539(i), i=0..28);

MotzkinNumber[n_] := Sum[ Binomial[n+1, k]*Binomial[n+1-k, k-1], {k, 0, Ceiling[(n+1)/2]}]/(n+1); a[0] = a[1] = 0; a[n_] := CatalanNumber[n] - (n-1)*MotzkinNumber[n-2] - MotzkinNumber[n-1]; Table[a[n], {n, 0, 28}] (* Jean-François Alcover, Jun 27 2013, from 3rd formula *)

def A217539(n):
    @CachedFunction
    def M(n): return (3*(n-1)*M(n-2)+(2*n+1)*M(n-1))/(n+2) if n>1 else 1
    @CachedFunction
    def catalan(n): return ((4*n-2)*catalan(n-1))/(n+1) if n>0 else 1
    return catalan(n) - (n-1)*M(n-2) - M(n-1) if n!=0 else 0
[A217539(i) for i in (0..28)]

a(n) = Sum_{k < 0} A217540(n, k).
a(n) = A000108(n) - A189912(n-1) for n > 0.
a(n) = C(n)-(n-1)*M(n-2)-M(n-1) for n > 0; C(n) Catalan, M(n) Motzkin numbers.
Conjecture: 2*(n+1)*(n-3)*a(n) +(-15*n^2+53*n-12)*a(n-1) +(28*n^2-157*n+165)*a(n-2) + 3*(3*n^2+2*n-26)*a(n-3) -18*(2*n-7)*(n-4)*a(n-4)=0. - R. J. Mathar, Nov 11 2012

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).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A113682 Expansion of 2/(sqrt(1-2x-3x^2)(1+x+sqrt(1-2x-3*x^2))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

SageMath

Formula

A217539 Number of Dyck paths of semilength n which satisfy the condition: number of returns + number of hills < number of peaks.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

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).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A113682 Expansion of 2/(sqrt(1-2*x-3*x^2)*(1+x+sqrt(1-2*x-3*x^2))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

SageMath

Formula

A217539 Number of Dyck paths of semilength n which satisfy the condition: number of returns + number of hills < number of peaks.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A113682 Expansion of 2/(sqrt(1-2x-3x^2)(1+x+sqrt(1-2x-3*x^2))).