|
%I #37 Mar 27 2022 23:28:48
%S 1,1,2,4,9,23,63,178,514,1515,4545,13827,42540,132124,413741,1304891,
%T 4141198,13214815,42375461,136478383,441285890,1431925180,4661485203,
%U 15219836738,49827678840,163535624722,537962562453,1773437280323
%N Number of Dyck paths of semilength n that do not contain the string UDDU.
%C Top left terms of powers of the production matrix M generates sequence A102403. - _Gary W. Adamson_, Jan 30 2012
%H Alois P. Heinz, <a href="/A135307/b135307.txt">Table of n, a(n) for n = 0..1000</a>
%H Eric S. Egge, Kailee Rubin, <a href="http://arxiv.org/abs/1508.05310">Snow Leopard Permutations and Their Even and Odd Threads</a>, arXiv:1508.05310 [math.CO], 2015
%H A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.
%F G.f.: f(x) satisfies x*f(x)^3 - (x+1)*f(x)^2 + (2*x+1)*f(x) - x = 0 . - _Eric Rowland_, Mar 29 2013
%F The Sapounakis et al. reference gives an explicit formula.
%F From _Gary W. Adamson_, Jan 30 2012: (Start)a(n) is the sum of top row terms in M^(n-1), where M = the following infinite square production matrix:
%F 1, 1, 0, 0, 0, 0, ...
%F 0, 1, 1, 0, 0, 0, ...
%F 1, 0, 1, 1, 0, 0, ...
%F 1, 1, 0, 1, 1, 0, ...
%F 1, 1, 1, 0, 1, 1, ... (End)
%F a(n) ~ sqrt(8 + 5*sqrt(2) + sqrt(2*(11 + 8*sqrt(2))/7))/4 * ((1 + sqrt(13 + 16*sqrt(2)))/2)^n / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Jan 27 2015
%e a(6) = 63 since the top row of M^5 = (17, 17, 13, 10, 5, 1), sum of terms = 63.
%p A135306 := proc(n,k) if n =0 then 1 ; else add((-1)^(j-k)*binomial(n-k,j-k)*binomial(2*n-3*j,n-j+1),j=k..floor((n-1)/2)) ; %*binomial(n,k)/n ; fi ; end: A135307 := proc(n) A135306(n,0) ; end: for n from 0 to 30 do printf("%a, ",A135307(n)) ; od: # _R. J. Mathar_, Dec 08 2007
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n<4, [1$2, 2, 4][n+1],
%p (2*n*(n-1)*(28*n^2-56*n-3)*a(n-1)
%p +(140*n^4-630*n^3+1063*n^2-699*n+144)*a(n-2)
%p -12*(n-3)*(14*n^3-42*n^2+16*n+21)*a(n-3)
%p +23*(n-3)*(n-4)*(28*n^2-14*n-3)*a(n-4))/
%p (n*(n+1)*(28*n^2-70*n+39)))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Sep 13 2014
%t a[n_] := Sum[(-1)^j*Binomial[n, j]*Binomial[2*n-3*j, n-j+1], {j, 0, (n-1)/2}]/n; a[0] = 1; Table[a[n], {n, 0, 27}] (* _Jean-François Alcover_, Nov 27 2014, after _R. J. Mathar_ *)
%Y Leading column of A135306.
%Y Cf. A102403.
%Y Column k=9 of A243753.
%K nonn,easy
%O 0,3
%A _N. J. A. Sloane_, Dec 07 2007
%E More terms from _R. J. Mathar_, Dec 08 2007
|
