|
| |
|
|
A052709
|
|
Expansion of g.f. (1-sqrt(1-4*x-4*x^2))/(2*(1+x)).
|
|
42
|
|
|
|
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, 127100310290431, 578433619525633, 2638370120138751
(list;
graph;
refs;
listen;
history;
text;
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, Dec 21 2003
Also, a(n+1) is the number of walks from (0,0) to (n,0) using steps (1,1), (1,-1) and (0,-1). See the U(n,k) array in A071943, where A052709(n+1) = U(n,0). - N. J. A. Sloane, Mar 29 2013
Conjecture: For n > 0, also the number of sequences of length n - 1 covering an initial interval of positive integers and avoiding three terms (..., x, ..., y, ..., z, ...) such that x <= y <= z. The version avoiding the strict pattern (1,2,3) is A226316. Sequences covering an initial interval are counted by A000670. The a(1) = 1 through a(4) = 9 sequences are:
() (1) (1,1) (1,2,1)
(1,2) (1,3,2)
(2,1) (2,1,1)
(2,1,2)
(2,1,3)
(2,2,1)
(2,3,1)
(3,1,2)
(3,2,1)
(End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{k=0..floor((n-1)/2)} (2*n-2-2*k)!/(k!*(n-k)!*(n-1-2*k)!). - Emeric Deutsch, Nov 14 2001
D-finite with recurrence: 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-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} Catalan(k)*binomial(k, n-k). - Paul Barry, Feb 22 2005
G.f. is x*c(x*(1+x)) where c(x) is the g.f. of A000108.
a(n+1) = (1/(2*Pi))*Integral_{x=2-2*sqrt(2)..2+2*sqrt(2)} x^n*(4+4x-x^2)/(2*(1+x)). - Paul Barry, Apr 01 2007
For n>0, a(n) is the upper left term in M^(n-1), where M is 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)
G.f.: x*Q(0), where Q(k) = 1 + (4*k+1)*x*(1+x)/(k+1 - x*(1+x)*(2*k+2)*(4*k+3)/(2*x*(1+x)*(4*k+3) + (2*k+3)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
a(n) ~ sqrt(2-sqrt(2))*2^(n-1/2)*(1+sqrt(2))^(n-1)/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Jun 29 2013
|
|
|
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 *)
CoefficientList[Series[(1 -Sqrt[1 -4x -4x^2])/(2(1+x)), {x, 0, 33}], x] (* Vincenzo Librandi, Feb 12 2016 *)
|
|
|
PROG
|
(PARI) a(n)=polcoeff((1-sqrt(1-4*x*(1+x+O(x^n))))/2/(1+x), n)
(Magma) [0] cat [(&+[Binomial(n, k+1)*Binomial(2*k, n-1): k in [0..n-1]])/n: n in [1..30]]; // G. C. Greubel, May 30 2022
(SageMath) [sum(binomial(k, n-k-1)*catalan_number(k) for k in (0..n-1)) for n in (0..30)] # G. C. Greubel, May 30 2022
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
|
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000
|
|
|
STATUS
|
approved
|
| |
|
|
