OFFSET
0,2
COMMENTS
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
LINKS
Muniru A Asiru, Table of n, a(n) for n = 0..300
FORMULA
A073155(n+1) = Sum_{k=0..n} a(k)*a(n-k), that is, convolution yields sequence A073155 minus the 0th term.
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);
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
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
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
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
From Peter Bala, Aug 25 2024: (Start)
(1/x) * series_reversion(x/A(x)) = 1 + 2*x + 9*x^2 + 56*x^3 + 400*x^4 + 3095*x^5 + 25240*x^6 + ... is the g.f. of A198953.
(1/x) * series_reversion(x*A(-x)) = 1 + 2*x + 3*x^2 + 8*x^3 + 25*x^4 + 83*x^5 + 289*x^6 + ... = G(x) + x, where G(x) = (1 - x^2 - sqrt(1 - 4*x - 2*x^2 + x^4))/(2*x) is the g.f. of A143330. (End)
Define a sequence operator R: {u(n): n >= 0} -> {v(n): n >= 0} by Sum_{n >= 0} v(n)*x^n = (1/x) * series_reversion(x/Sum_{n >= 0} u(n)*x^n). Then R({a(n)}) = A198953, R^2({a(n)}) = A215715 and R^3({a(n)}) = A364335. Cf. A216359. - Peter Bala, Sep 13 2024
EXAMPLE
G.f.: A(x) = 1 + 2*x + 5*x^2 + 18*x^3 + 70*x^4 + 293*x^5 + 1283*x^6 + ...
MAPLE
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
MATHEMATICA
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 *)
PROG
(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 */
(Maxima)
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 */
(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
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Paul D. Hanna, Jul 29 2002
EXTENSIONS
More terms from Paul D. Hanna, Mar 03 2008
New name using a comment from David Callan, Peter Luschny, Oct 14 2018
STATUS
approved