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

Author

Emeric Deutsch, Oct 07 2007

Keywords

• nonn

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

Examples

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

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.
• Mark Shattuck, Subword Patterns in Smooth Words, Enum. Comb. Appl. (2024) Vol. 4, No. 4, Art. No. S2R32. See p. 6.

Crossrefs

Cf. A005773, A107230, A132893.

Column k=1 of A328347.

Programs

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

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

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