|
|
A005572
|
|
Number of walks on cubic lattice starting and finishing on the xy plane and never going below it.
(Formerly M3539)
|
|
28
|
|
|
1, 4, 17, 76, 354, 1704, 8421, 42508, 218318, 1137400, 5996938, 31940792, 171605956, 928931280, 5061593709, 27739833228, 152809506582, 845646470616, 4699126915422, 26209721959656, 146681521121244, 823429928805936
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Also number of paths from (0,0) to (n,0) in an n X n grid using only Northeast, East and Southeast steps and the East steps come in four colors. - Emeric Deutsch, Nov 03 2002
Number of skew Dyck paths of semilength n+1 with the left steps coming in two colors. - David Scambler, Jun 21 2013
Number of 2-colored Schroeder paths from (0,0) to (2n+2,0) with no level steps H=(2,0) at an even level. There are two ways to color an H-step at an odd level. Example: a(1)=4 because we have UUDD, UHD (2 choices) and UDUD. - José Luis Ramírez Ramírez, Apr 27 2015
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
Generating function A(x) satisfies 1 + (xA)^2 = A - 4xA.
a(0) = 1 and, for n > 0, a(n) = 4a(n-1) + Sum_{i=1..n-1} a(i-1)*a(n-i-1). - John W. Layman, Jan 07 2000
G.f.: (1 - 4*x - sqrt(1 - 8*x + 12*x^2))/(2*x^2).
D-finite with recurrence: a(n) = ((2*n+1)*a(n-1) - 3*(n-1)*a(n-2))*4/(n+2), n > 0.
Let A(x) be the g.f., then B(x) = 1 + x*A(x) = 1 + 1*x + 4*x^2 + 17*x^3 + ... = 1/(1-z/(1-z/(1-z/(...)))) where z=x/(1-2*x) (continued fraction); more generally B(x) = C(x/(1-2*x)) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011
a(n) = sum of top row terms of M^n, M = an infinite square production matrix as follows:
3, 1, 0, 0, ...
1, 3, 1, 0, ...
1, 1, 3, 1, ...
1, 1, 1, 3, ...
... (End)
a(n) = Sum_{k=0..floor(n/2)} binomial(n,2*k) * binomial(2k,k) * 4^(n-2k) / (k+1). - Max Alekseyev, Feb 02 2015
a(n) = Sum_{k=0..n} binomial(n,k) * 2^(n-k) * binomial(2*k+2, k)/(k+1).
a(n) = Sum_{k=0..n} binomial(n,k) * 2^(n-k) * A000108(k+1).
a(n) = [x^n] (1 + 4*x + x^2)^(n+1) / (n+1).
G.f.: (1/x) * Series_Reversion( x/(1 + 4*x + x^2) ). (End)
a(n) = 2^n*hypergeom([3/2, -n], [3], -2). - Peter Luschny, Feb 03 2015
a(n) = 4^n*hypergeom([-n/2, (1-n)/2], [2], 1/4). - Robert Israel, Feb 04 2015
a(n) = 2*(12^(n/2))*(n!/(n+2)!)*GegenbauerC(n, 3/2,2/sqrt(3)), where GegenbauerC are Gegenbauer polynomials in Maple notation. This is a consequence of Robert Israel's formula. - Karol A. Penson, Feb 20 2015
a(n) = (2^(n+1)*3^((n+1)/2)*P(n+1,1,2/sqrt(3)))/((n+1)*(n+2)) where P(n,u,x) are the associated Legendre polynomials of the first kind. - Peter Luschny, Feb 24 2015
a(n) = -6^(n+1)*sqrt(3)*Integral{t=0..Pi}(cos(t)*(2+cos(t))^(-n-2))/(Pi*(n+2)). - Peter Luschny, Feb 24 2015
Integral representation as the n-th moment of a positive function defined on a segment x=[2, 6]. This function is the Wigner's semicircle distribution shifted to the right by 4. This representation is unique. In Maple notation,
a(n) = int(x^n*sqrt(4-(x-4)^2)/(2*Pi), x=2..6),
a(n) = 2*6^n*Pochhammer(3/2, n)*hypergeom([-n, 3/2], [-n-1/2], 1/3)/(n+2)!
(End)
a(n) = GegenbauerC(n, -n-1, -2)/(n+1). - Peter Luschny, May 09 2016
G.f. A(x) = 1/(1 - 2*x)*c(x/(1 - 2*x))^2, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. Cf. A129400.
Conjecture: a(n) is even except for n of the form 2*(2^k - 1). (End)
|
|
EXAMPLE
|
a(3) = 76 = sum of top row terms of M^3; i.e., (37 + 29 + 9 + 1).
|
|
MAPLE
|
a := n -> simplify(2^n*hypergeom([3/2, -n], [3], -2)):
a := n -> simplify(GegenbauerC(n, -n-1, -2))/(n+1):
|
|
MATHEMATICA
|
RecurrenceTable[{a[0]==1, a[1]==4, a[n]==((2n+1)a[n-1]-3(n-1)a[n-2]) 4/(n+2)}, a[n], {n, 30}] (* Harvey P. Dale, Oct 04 2011 *)
a[n_]:=If[n==0, 1, Coefficient[(1+4x+x^2)^(n+1), x^n]/(n+1)]
|
|
PROG
|
(PARI) a(n)=polcoeff((1-4*x-sqrt(1-8*x+12*x^2+x^3*O(x^n)))/2, n+2)
(PARI) { A005572(n) = sum(k=0, n\2, binomial(n, 2*k) * binomial(2*k, k) * 4^(n-2*k) / (k+1) ) } /* Max Alekseyev, Feb 02 2015 */
(PARI) {a(n)=sum(k=0, n, binomial(n, k) * 2^(n-k) * binomial(2*k+2, k)/(k+1) )}
(Maxima) a(n):=coeff(expand((1+4*x+x^2)^(n+1)), x^n)/(n+1); makelist(a(n), n, 0, 12); /* Emanuele Munarini, Apr 06 2012 */
(Sage)
A108198 = lambda n, k: (-1)^k*catalan_number(k+1)*rising_factorial(-n, k)/factorial(k)
return sum(A108198(n, k)*2^(n-k) for k in (0..n))
|
|
CROSSREFS
|
Binomial transform of A002212. Sequence shifted right twice is A025228.
|
|
KEYWORD
|
nonn,walk,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|