|
%I #39 Oct 14 2018 11:56:32
%S 1,2,5,18,70,293,1283,5808,26960,127628,613814,2990681,14730713,
%T 73229291,366936231,1851352820,9397497758,47957377934,245903408244,
%U 1266266092112,6545667052320,33954266444498,176689391245146
%N Number of Schroeder n-paths containing no FFs.
%C Number of Schroeder n-paths containing no FFs. A Schroeder n-path (A006318) consists of steps U=(1,1),F=(2,0),D=(1,-1) starting at (0,0), ending at (2n,0), and never going below the x-axis. Example: a(2)=5 counts UFD, UUDD, UDF, FUD, UDUD. - _David Callan_, Aug 23 2011
%H Muniru A Asiru, <a href="/A073157/b073157.txt">Table of n, a(n) for n = 0..300</a>
%F A073155(n+1) = Sum_{k=0..n} a(k)*a(n-k), that is, convolution yields sequence A073155 minus the 0th term.
%F G.f.: A(x) = (1 - sqrt(1 - 4*x*(1+x)^2))/(2*x*(1+x)) satisfies A(x) = (1+x)*(1 + x*A(x)^2);
%F G.f.: A(x) = (1+x)*C(x*(1+x)^2) where C(x) is the Catalan g.f. of A000108. - _Paul D. Hanna_, Mar 03 2008
%F a(n) = Sum_{j=0..n}((Sum_{k=0..j}((binomial(2*k+2,j-k)*C(k))))*(-1)^(n-j)), where C(k) = A000108(k). - _Vladimir Kruchinin_, Mar 13 2016
%F a(n) = Sum_{i=0..n} C(2*i+1,i)*C(2*i+1,n-i))/(2*i+1). - _Vladimir Kruchinin_, Oct 11 2018
%F Recurrence: (n+1)*a(n) = 3*(n-1)*a(n-1) + 6*(2*n - 3)*a(n-2) + 6*(2*n - 5)*a(n-3) + 2*(2*n - 7)*a(n-4). - _Vaclav Kotesovec_, Oct 11 2018
%e G.f.: A(x) = 1 + 2*x + 5*x^2 + 18*x^3 + 70*x^4 + 293*x^5 + 1283*x^6 + ...
%p a:=n->add(binomial(2*i+1,i)*binomial(2*i+1,n-i)/(2*i+1),i=0..n): seq(a(n),n=0..25); # _Muniru A Asiru_, Oct 11 2018
%t Table[Sum[Binomial[2*i + 1, i]*Binomial[2*i + 1, n - i]/(2*i + 1), {i, 0, n}], {n, 0, 25}] (* _Vaclav Kotesovec_, Oct 11 2018 *)
%o (PARI) {a(n)=local(A=1); for(i=0,n-1,A=(1+x)*(1+x*(A+x*O(x^n))^2));polcoeff(A,n)} /* _Paul D. Hanna_, Mar 03 2008 */
%o (Maxima)
%o a(n):=sum((sum((binomial(2*k+2,j-k)*binomial(2*k,k)/(k+1)),k,0,j))*(-1)^(n-j),j,0,n); /* _Vladimir Kruchinin_, Mar 13 2016 */
%o (GAP) List([0..25],n->Sum([0..n],i->Binomial(2*i+1,i)*Binomial(2*i+1,n-i)/(2*i+1))); # _Muniru A Asiru_, Oct 11 2018
%Y Leftmost column of triangle A073154 (was previous name).
%Y Cf. A073155, A073156, A073153, A000108.
%K easy,nonn
%O 0,2
%A _Paul D. Hanna_, Jul 29 2002
%E More terms from _Paul D. Hanna_, Mar 03 2008
%E New name using a comment from _David Callan_, _Peter Luschny_, Oct 14 2018
|
