A132894 Number of (1,0) steps in all paths of length n with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., in all length-n left factors of Motzkin paths).

0, 1, 4, 15, 52, 175, 576, 1869, 6000, 19107, 60460, 190333, 596652, 1863745, 5804176, 18028755, 55873872, 172818243, 533589660, 1644921789, 5063762220, 15568666029, 47811348816, 146675181975, 449538774048, 1376564658525

Offset

0,3

Comments

Number of peaks (i.e., UDs) in all paths of length n+1 with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., in all length n+1 left factors of Motzkin paths). Example: a(2)=4 because in the 13 (=A005773(4)) length-3 left factors of Motzkin paths, namely HHH, HHU, H(UD), HUH, HUU, (UD)H, (UD)U, UHD, UHH, UHU, U(UD), UUH and UUU, we have altogether 4 peaks (shown between parentheses).

This could be called the Motzkin transform of A077043 because the substitution x -> x*A001006(x) in the independent variable of the g.f. of A077043 yields the g.f. of this sequence here. - R. J. Mathar, Nov 10 2008

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

A. Asinowski and G. Rote, Point sets with many non-crossing matchings, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.

Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv preprint arXiv:1203.6792, 2012; and also, J. Int. Seq. 17 (2014) #14.1.5.

Formula

a(n) = Sum_{k=0..n} k*A107230(n,k).

a(n) = Sum_{k=0..floor((n+1)/2)} k*A132893(n+1,k).

a(n) = Sum_{k=0..n} k*C(n,k)*C(n-k, floor((n-k)/2)).

G.f.: z/((1-3*z)*sqrt(1-2*z-3*z^2)).

a(n) = Sum_{k=0..n} k*C(n,k)*C(2*k,k)*(-1)^(n-k). - Wadim Zudilin, Oct 11 2010

E.g.f.: exp(x)*x*(BesselI(0, 2*x) + BesselI(1, 2*x)). - Peter Luschny, Aug 25 2012

a(n) = 2*n/(n-1)*a(n-1) + 3*a(n-2) for n>=2, a(n) = n for n<2. a(n) = n*A005773(n). - Alois P. Heinz, Jul 15 2013

a(n) ~ 3^(n-1/2)*sqrt(n/Pi). - Vaclav Kotesovec, Oct 08 2013

a(n) = (-1)^(n+1)*JacobiP(n-1,1,-n+1/2,-7). - Peter Luschny, Sep 23 2014

Example

a(2) = 4 because in the 5 (=A005773(3)) length-2 left factors of Motzkin paths, namely HH, HU, UD, UH and UU, we have altogether 4 H steps.
G.f. = x + 4*x^2 + 15*x^3 + 52*x^4 + 175*x^5 + 576*x^6 + 1869*x^7 + 6000*x^8 + ...

Maple

a := n -> add(k*binomial(n, k)*binomial(n-k, floor((n-k)/2)), k=0..n): seq(a(n), n=0..25);
# second Maple program:
a:= proc(n) a(n):=`if`(n<2, n, 2*n/(n-1)*a(n-1)+3*a(n-2)) end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 15 2013

Mathematica

a[n_] := n*Hypergeometric2F1[3/2, 1-n, 2, 4]; Table[ a[n] // Abs, {n, 0, 25}] (* Jean-François Alcover, Jul 10 2013 *)
a[ n_] := If[ n < 0, 0, -(-1)^n n Hypergeometric2F1[ 3/2, 1 - n, 2, 4]]; (* Michael Somos, Aug 06 2014 *)

Prog

(Sage)
A132894 = lambda n: (-1)^(n+1)*jacobi_P(n-1, 1, -n+1/2, -7)
[Integer(A132894(n).n(40), 16) for n in range(26)] # Peter Luschny, Sep 23 2014

Crossrefs

Cf. A005773, A107230, A132893.

Column k=1 of A328347.

Sequence in context: A291011 A137213 A027853 * A117917 A192431 A329253

Adjacent sequences: A132891 A132892 A132893 * A132895 A132896 A132897

Keyword

nonn

Author

Emeric Deutsch, Oct 07 2007

Status

approved