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.
Mark Shattuck, Subword Patterns in Smooth Words, Enum. Comb. Appl. (2024) Vol. 4, No. 4, Art. No. S2R32. See p. 6.
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Oct 07 2007
STATUS
approved