|
| |
|
|
A052709
|
|
G.f.: (1-sqrt(1-4x-4x^2))/(2(1+x)).
|
|
15
| |
|
|
0, 1, 1, 3, 9, 31, 113, 431, 1697, 6847, 28161, 117631, 497665, 2128127, 9183489, 39940863, 174897665, 770452479, 3411959809, 15181264895, 67833868289, 304256253951, 1369404661761, 6182858317823, 27995941060609
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| A simple context-free grammar.
Number of lattice paths from (0,0) to (2n-2,0) that stay (weakly) in the first quadrant and such that each step is either U=(1,1),D=(1,-1), or L=(3,1). Equivalently, underdiagonal lattice paths from (0,0) to (n-1,n-1) and such that each step is either (1,0),(0,1), or (2,1). E.g. a(4)=9 because in addition to the five Dyck paths from (0,0) to (6,0) [UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD] we have LDUD, LUDD, ULDD and UDLD. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 21 2003
Hankel transform of a(n+1) is A006125(n+1). - Paul Barry (pbarry(AT)wit.ie), Apr 01 2007
|
|
|
REFERENCES
| Drake, Brian, Limits of areas under lattice paths. Discrete Math. 309 (2009), no. 12, 3936-3953.
N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
|
|
|
LINKS
| L. Ferrari, E. Pergola, R. Pinzani and S. Rinaldi, Jumping succession rules and their generating functions, Discrete Math., 271 (2003), 29-50.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 664
D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.
|
|
|
FORMULA
| a(n)=sum((2*n-2-2*k)!/k!/(n-k)!/(n-1-2*k)!, k=0..floor((n-1)/2)). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 14 2001
n*a(n)=(3*n-6)*a(n-1)+(8*n-18)*a(n-2)+(4*n-12)*a(n-3), n>2. a(1)=a(2)=1.
a(n)=b(1)*a(n-1)+b(2)*a(n-2)+...+b(n-1)*a(1) for n>1 where b(n)=A025227(n).
G.f.: A(x) = x/(1-(1+x)*A(x)). [Paul D. Hanna (pauldhanna(AT)juno.com), Aug 16 2002]
G.f.: A(x) = x/(1-z/(1-z/(1-z/(...)))) where z=x+x^2 (continued fraction). [Paul D. Hanna, Aug 16 2002; revised by Joerg Arndt, Mar 18 2011].
a(n+1)=sum{k=0..n, C(k)*C(k, n-k)} - Paul Barry (pbarry(AT)wit.ie), Feb 22 2005
G.f. is x*c(x*(1+x)) where c(x) is the g.f. of A000108. Row sums of A117434. - Paul Barry (pbarry(AT)wit.ie), Mar 14 2006
a(n+1)=(1/(2*pi))*int(x^n*(4+4x-x^2)/(2(1+x)),x,2-2*sqrt(2),2+2*sqrt(2)); - Paul Barry (pbarry(AT)wit.ie), Apr 01 2007
From Gary W. Adamson, Jul 22 2011: (start) a(n), n>0 = upper left term in M^(n-1), where M = an infinite square production matrix as follows:
1, 1, 0, 0, 0, 0,...
2, 1, 1, 0, 0, 0,...
2, 2, 1, 1, 0, 0,...
2, 2, 2, 1, 1, 0,...
2, 2, 2, 2, 1, 1,...
... (end)
|
|
|
MAPLE
| spec := [S, {C=Prod(B, Z), S=Union(B, C, Z), B=Prod(S, S)}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
|
|
|
MATHEMATICA
| InverseSeries[Series[(y-y^2)/(1+y^2), {y, 0, 24}], x] (* then A(x)= y(x) *) - Len Smiley Apr 12 2000
|
|
|
PROG
| (PARI) a(n)=polcoeff((1-sqrt(1-4*x*(1+x+O(x^n))))/2/(1+x), n)
|
|
|
CROSSREFS
| A025227(n)=a(n)+a(n-1).
Diagonal entries of A071945.
Sequence in context: A056335 A049188 A049165 * A049179 A049154 A110136
Adjacent sequences: A052706 A052707 A052708 * A052710 A052711 A052712
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| encyclopedia(AT)pommard.inria.fr, Jan 25 2000
|
|
|
EXTENSIONS
| Better g.f. and recurrence from Michael Somos, Aug 03 2000
More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000
|
| |
|
|
