A176697 G.f. satisfies: A(x) = 1 + x^2 + x*A(x)^2.

1, 1, 3, 7, 20, 63, 208, 711, 2496, 8944, 32578, 120263, 448938, 1691776, 6427130, 24589043, 94653498, 366344216, 1424750506, 5565002716, 21821377624, 85867522754, 338974659036, 1342074448663, 5327845401606, 21203102693634, 84574191671494, 338060063747476

Offset

0,3

Comments

A recursive sequence of vectors: a(n) = vector(a(0),...,a(n-1)) * Reverse(vector(a(0),...,a(n-1)) with a(0) = a(1) = 1, a(2) = 3.

Number of Schroeder paths in which horizontal sequences are always exactly HH and never precede an up step. - David Scambler, May 23 2012

References

F. S. Roberts, Applied Combinatorics, Prentice-Hall, 1984, p. 231.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

G.f.: A(x) = (1 - sqrt(1 - 4*x*(1+x^2)))/(2*x). [Paul D. Hanna, Nov 12 2011]

a(n) = Sum_{i=1..n} a(i-1)*a(n-i) for n>2; a(0) = a(1) = 1, a(2) = 3. - Alois P. Heinz, May 24 2012

Recurrence: (n+1)*a(n) = 2*(2*n-1)*a(n-1) + 2*(2*n-7)*a(n-3). - Vaclav Kotesovec, Sep 11 2013

a(n) ~ sqrt(3-8*z)/(4*sqrt(Pi)*n^(3/2)*z^(n+1)), where z = (9+sqrt(273))^(1/3)/(2*3^(2/3)) - 2/(3*(9+sqrt(273)))^(1/3) = 0.236732903864563... is the root of the equation 4*z*(1+z^2)=1. - Vaclav Kotesovec, Sep 11 2013

a(n) = sum(m=0..n/2, binomial(n-2*m+1,m)*binomial(2*(n-2*m),n-2*m)/(n+1-2*m)). - Vladimir Kruchinin, Nov 21 2014

Maple

a:= proc(n) a(n):= add(a(i-1)*a(n-i), i=1..n) end:
a(0), a(1), a(2):= 1, 1, 3:
seq(a(n), n=0..30);  # Alois P. Heinz, May 24 2012

Mathematica

a[0] := 1; a[1] := 1; a[2] := 3; a[n_] := a[n] = Table[a[i], {i, 0, n - 1}].Table[a[n - 1 - i], {i, 0, n - 1}]; Table[a[n], {n, 0, 30}]
f[x_, y_, d_]:=f[x, y, d] = If[x<0||y<x, 0, If[x==0&&y==0, 1, If[d==0, f[x-1, y, -1], f[x-1, y, -1]+f[x, y-1, 1]+f[x-2, y-2, 0]]]]; Table[f[n, n, -1], {n, 0, 30}] (* David Scambler, May 24 2012 *)

Prog

(PARI) {a(n)=polcoeff((1 - sqrt(1 - 4*x*(1+x^2) +x^2*O(x^n)))/(2*x), n)} /* Paul D. Hanna */
(Maxima)
a(n):=sum(binomial(n-2*m+1, m)*binomial(2*(n-2*m), n-2*m)/(n+1-2*m), m, 0, (n)/2); /* Vladimir Kruchinin_, Nov 21 2014 */

Crossrefs

Sequence in context: A361625 A056783 A320735 * A320736 A320737 A320738

Adjacent sequences: A176694 A176695 A176696 * A176698 A176699 A176700

Keyword

nonn

Author

Roger L. Bagula, Apr 24 2010

Extensions

Name changed by Paul D. Hanna, Nov 12 2011

Status

approved