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

%I #55 Sep 05 2024 14:33:34

%S 0,1,4,15,52,175,576,1869,6000,19107,60460,190333,596652,1863745,

%T 5804176,18028755,55873872,172818243,533589660,1644921789,5063762220,

%U 15568666029,47811348816,146675181975,449538774048,1376564658525

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

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

%C 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

%H Alois P. Heinz, <a href="/A132894/b132894.txt">Table of n, a(n) for n = 0..1000</a>

%H A. Asinowski and G. Rote, <a href="http://arxiv.org/abs/1502.04925">Point sets with many non-crossing matchings</a>, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.

%H Luca Ferrari and Emanuele Munarini, <a href="http://arxiv.org/abs/1203.6792">Enumeration of edges in some lattices of paths</a>, arXiv preprint arXiv:1203.6792, 2012; and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Ferrari/ferrari.html">also</a>, J. Int. Seq. 17 (2014) #14.1.5.

%H Mark Shattuck, <a href="https://doi.org/10.54550/ECA2024V4S4R32">Subword Patterns in Smooth Words</a>, Enum. Comb. Appl. (2024) Vol. 4, No. 4, Art. No. S2R32. See p. 6.

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

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

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

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

%F a(n) = Sum_{k=0..n} k*C(n,k)*C(2*k,k)*(-1)^(n-k). - _Wadim Zudilin_, Oct 11 2010

%F E.g.f.: exp(x)*x*(BesselI(0, 2*x) + BesselI(1, 2*x)). - _Peter Luschny_, Aug 25 2012

%F 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

%F a(n) ~ 3^(n-1/2)*sqrt(n/Pi). - _Vaclav Kotesovec_, Oct 08 2013

%F a(n) = (-1)^(n+1)*JacobiP(n-1,1,-n+1/2,-7). - _Peter Luschny_, Sep 23 2014

%e 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.

%e G.f. = x + 4*x^2 + 15*x^3 + 52*x^4 + 175*x^5 + 576*x^6 + 1869*x^7 + 6000*x^8 + ...

%p a := n -> add(k*binomial(n, k)*binomial(n-k, floor((n-k)/2)), k=0..n): seq(a(n), n=0..25);

%p # second Maple program:

%p a:= proc(n) a(n):=`if`(n<2, n, 2*n/(n-1)*a(n-1)+3*a(n-2)) end:

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Jul 15 2013

%t a[n_] := n*Hypergeometric2F1[3/2, 1-n, 2, 4]; Table[ a[n] // Abs, {n, 0, 25}] (* _Jean-François Alcover_, Jul 10 2013 *)

%t a[ n_] := If[ n < 0, 0, -(-1)^n n Hypergeometric2F1[ 3/2, 1 - n, 2, 4]]; (* _Michael Somos_, Aug 06 2014 *)

%o (Sage)

%o A132894 = lambda n: (-1)^(n+1)*jacobi_P(n-1,1,-n+1/2,-7)

%o [Integer(A132894(n).n(40),16) for n in range(26)] # _Peter Luschny_, Sep 23 2014

%Y Cf. A005773, A107230, A132893.

%Y Column k=1 of A328347.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Oct 07 2007