login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 6
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 (list; graph; refs; listen; history; text; internal format)
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, G. Rote, Point sets with many non-crossing matchings, arXiv preprint arXiv:1502.04925, 2015

Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv preprint arXiv:1203.6792, 2012 and 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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 28 00:28 EST 2020. Contains 332319 sequences. (Running on oeis4.)