A073157 Number of Schroeder n-paths containing no FFs.

1, 2, 5, 18, 70, 293, 1283, 5808, 26960, 127628, 613814, 2990681, 14730713, 73229291, 366936231, 1851352820, 9397497758, 47957377934, 245903408244, 1266266092112, 6545667052320, 33954266444498, 176689391245146

Offset: 0

Author

Paul D. Hanna, Jul 29 2002

Keywords

• easy
• nonn

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

Examples

			G.f.: A(x) = 1 + 2*x + 5*x^2 + 18*x^3 + 70*x^4 + 293*x^5 + 1283*x^6 + ...
		

Links

• Muniru A Asiru, Table of n, a(n) for n = 0..300

Crossrefs

Leftmost column of triangle A073154 (was previous name).

Cf. A000108, A073155, A073156, A073153, A143330, A198953, A215715, A216359, A364335, A364371.

Programs

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

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 *)

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 */

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 */

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

Extensions

More terms from Paul D. Hanna, Mar 03 2008

New name using a comment from David Callan, Peter Luschny, Oct 14 2018