|
%I #45 Jan 31 2024 08:03:45
%S 1,1,1,2,5,12,29,72,183,473,1239,3282,8777,23665,64261,175584,482395,
%T 1331795,3692891,10280190,28719659,80493514,226268539,637767720,
%U 1802113489,5103874135,14485789561,41194844114,117366166381
%N Number of Motzkin paths of length n with no peaks at level 1.
%C Number of Motzkin paths starting with a maximal run of an even number of up-steps. - _Alexander Burstein_, Jan 30 2024
%C Number of compositions of n where there are [1, 0, 1, 2, 4, 9, 21, 51, 127, 323,...] (cf. A001006) sorts of part k (k>=1). - _Joerg Arndt_, Jan 31 2024
%H Fung Lam, <a href="/A089372/b089372.txt">Table of n, a(n) for n = 0..2000</a>
%H E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s46rinaldi.html">ECO method and hill-free generalized Motzkin paths</a>, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.
%H Qiang-Hui Guo, L. H. Sun, and J. Wang, <a href="https://doi.org/10.1007/s11538-016-0212-y">Regular Simple Queues of Protein Contact Maps</a>, Bulletin of Mathematical Biology, 2016, January 2017, Volume 79, Issue 1, pp 21-35.
%F G.f.: (1-z-q)/(z^2*(3-z-q)), where q = sqrt(1-2*z-3*z^2).
%F a(n) = sum(k=1..(n+3)/2, (k*sum(j=0..n-k+3, binomial(j,n-j+3)*binomial(n-k+3,j)))/(n-k+3)*(-1)^(k-1)). - _Vladimir Kruchinin_, Oct 22 2011
%F G.f.: 1/(1-z-z^3*M-z^4*M^2), where M is the g.f. of the Motzkin Numbers. - _José Luis Ramírez Ramírez_, Jan 28 2013
%F Recurrence: 2*(n+2)*a(n) = 3*(n-1)*a(n-4) + (4-n)*a(n-3) + 3*(n-3)*a(n-2) + (5*n+4)*a(n-1). - _Fung Lam_, Feb 03 2014
%F Asymptotics: a(n) ~ 3^(n+4)/(2^5*sqrt(3*Pi*n^3)). - _Fung Lam_, Mar 31 2014
%F From _Alexander Burstein_, Jan 30 2024: (Start)
%F G.f.: M/(1+z^2*M), where M = M(z) is the g.f. of the Motzkin numbers, A001006.
%F G.f.: (1+M)/(2-z+z^2), where M = M(z) is the g.f. of the Motzkin numbers, A001006.
%F 2*a(n) - a(n-1) + a(n-2) = A001006(n) + (1 if n=0), where we let a(n)=0 if n<0. (End)
%e a(4)=5 because the Motzkin paths of length 4 with no peaks at level 1 are: HHHH, HUHD, UHDH, UHHD, and UUDD, where H=(1,0), U=(1,1) and D=(1,-1).
%e a(4)=5 because the Motzkin paths of length 4 starting with a maximal run of an even number of up-steps U are: HHHH, HHUD, HUHD, HUDH, and UUDD, where H=(1,0), U=(1,1) and D=(1,-1). - _Alexander Burstein_, Jan 30 2024
%t CoefficientList[Series[(1-x-Sqrt[1-2*x-3*x^2])/(x^2*(3-x-Sqrt[1-2*x-3*x^2])), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Mar 31 2014 *)
%o (Maxima)
%o a(n):=sum((k*sum(binomial(j,n-j+3)*binomial(n-k+3,j),j,0,n-k+3))/(n-k+3)*(-1)^(k-1),k,1,(n+3)/2); /* _Vladimir Kruchinin_, Oct 22 2011 */
%Y Cf. A001006.
%K nonn
%O 0,4
%A _Emeric Deutsch_, Dec 27 2003
|
