|
%I #63 Aug 29 2023 11:21:15
%S 1,1,2,3,6,11,23,47,102,221,493,1105,2516,5763,13328,30995,72556,
%T 170655,403351,957135,2279948,5449013,13063596,31406517,75701508,
%U 182902337,442885683,1074604289,2612341856,6361782007,15518343597,37912613631,92758314874
%N Number of Motzkin paths of length n with no level steps at odd level.
%C a(n) = number of Motzkin paths of length n that avoid UF. Example: a(3) counts FFF, UDF, FUD but not UFD. - _David Callan_, Jul 15 2004
%C Also, number of 1-2 trees with n edges and with thinning limbs. A 1-2 tree is an ordered tree with vertices of outdegree at most 2. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children. - _Emeric Deutsch_ and _Louis Shapiro_, Nov 04 2006
%H Alois P. Heinz, <a href="/A090344/b090344.txt">Table of n, a(n) for n = 0..1000</a>
%H Andrei Asinowski, Cyril Banderier, and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Barry3/barry93.html">Continued fractions and transformations of integer sequences</a>, JIS 12 (2009) 09.7.6.
%H Rui Duarte and António Guedes de Oliveira, <a href="https://www.cmup.pt/sites/default/files/2023-08/GF_LP_corrected_0.pdf">Generating functions of lattice paths</a>, Univ. do Porto (Portugal 2023).
%F G.f.: (1-x-sqrt(1-2*x-3*x^2+4*x^3))/(2*x^2*(1-x)).
%F G.f. satisfies: A(x) = 1/(1-x) + x^2*A(x)^2. - _Paul D. Hanna_, Jun 24 2012
%F D-finite with recurrence (n+2)*a(n) = 2*(n+1)*a(n-1) + (3*n-4)*a(n-2) - 2*(2*n-3)*a(n-3). - _Vladeta Jovovic_, Sep 11 2004
%F a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*binomial(2*k, k)/(k+1)). - _Paul Barry_, Nov 13 2004
%F a(n) = 1 + Sum_{k=1..n-1} a(k-1)*a(n-k-1). - _Henry Bottomley_, Feb 22 2005
%F G.f.: 1/(1-x-x^2/(1-x^2/(1-x-x^2/(1-x^2/(1-x-x^2/(1-x^2/(1-... (continued fraction). - _Paul Barry_, Apr 08 2009
%F With M = an infinite tridiagonal matrix with all 1's in the super and subdiagonals and [1,0,1,0,1,0,...] in the main diagonal and V = vector [1,0,0,0,...] with the rest zeros, the sequence starting with offset 1 = leftmost column iterates of M*V. - _Gary W. Adamson_, Jun 08 2011
%F Recurrence (an alternative): (n+2)*a(n) = 3*(n+1)*a(n-1) + (n-4)*a(n-2) - (7*n-13)*a(n-3) + 2*(2*n-5)*a(n-4), n>=4. - _Fung Lam_, Apr 01 2014
%F Asymptotics: a(n) ~ (8/(sqrt(17)-1))^n*( 1/17^(1/4) + 17^(1/4) )*17 /(16*sqrt(Pi*n^3)). - _Fung Lam_, Apr 01 2014
%e a(3)=3 because we have HHH, HUD and UDH, where U=(1,1), D=(1,-1) and H=(1,0).
%p C:=x->(1-sqrt(1-4*x))/2/x: G:=C(z^2/(1-z))/(1-z): Gser:=series(G,z=0,40): seq(coeff(Gser,z,n),n=0..36);
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n<3, (n^2-n+2)/2,
%p ((2*n+2)*a(n-1) -(4*n-6)*a(n-3) +(3*n-4)*a(n-2))/(n+2))
%p end:
%p seq(a(n), n=0..40); # _Alois P. Heinz_, May 17 2013
%t Table[HypergeometricPFQ[{1/2, (1-n)/2, -n/2}, {2, -n}, -16], {n, 0, 40}] (* _Jean-François Alcover_, Feb 20 2015, after _Paul Barry_ *)
%o (PARI) {a(n)=local(A=1+x);for(i=1,n,A=1/(1-x+x*O(x^n))+x^2*A^2+x*O(x^n));polcoeff(A,n)} \\ _Paul D. Hanna_, Jun 24 2012
%o (Magma) [(&+[Binomial(n-k, k)*Catalan(k): k in [0..Floor(n/2)]]): n in [0..40]]; // _G. C. Greubel_, Jun 15 2022
%o (SageMath) [sum(binomial(n-k,k)*catalan_number(k) for k in (0..(n//2))) for n in (0..40)] # _G. C. Greubel_, Jun 15 2022
%Y Cf. A001006, A086622, A098474, A124344, A124497.
%Y Cf. A014137, A023431, A144700.
%K nonn
%O 0,3
%A _Emeric Deutsch_, Jan 28 2004
|
