A005022 Number of walks of length 2n+6 in the path graph P_7 from one end to the other.

6, 26, 100, 364, 1288, 4488, 15504, 53296, 182688, 625184, 2137408, 7303360, 24946816, 85196928, 290926848, 993379072, 3391793664, 11580678656, 39539651584, 134998297600, 460915984384, 1573671536640, 5372862566400, 18344123969536, 62630804299776

Offset: 1

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn
• walk
• easy

Examples

			Example: a(1)=6 because in the path ABCDEFG we have ABABCDEFG, ABCBCDEFG, ABCDCDEFG, ABCDEDEFG, ABCDEFEFG and ABCDEFGFG. - _Emeric Deutsch_, Apr 02 2004
		

References

• W. Feller, An Introduction to Probability Theory and its Applications, 3rd ed, Wiley, New York, 1968, p. 96.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• C. J. Everett, P. R. Stein, The combinatorics of random walk with absorbing barriers, Discrete Math. 17 (1977), no. 1, 27-45.
• C. J. Everett, P. R. Stein, The combinatorics of random walk with absorbing barriers, Discrete Math. 17 (1977), no. 1, 27-45. [Annotated scanned copy]
• P. Flajolet, J.-C. Raoult, and J. Vuillemin, The number of registers required for evaluating arithmetic expressions, Theoret. Comput. Sci. 9 (1979), no. 1, 99-125.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• Xavier Gérard Viennot, A Strahler bijection between Dyck paths and planar trees. Formal power series and algebraic combinatorics (Barcelona, 1999). Discrete Math. 246 (2002), no. 1-3, 317--329. MR1887493 (2003b:05013).
• Index entries for linear recurrences with constant coefficients, signature (6,-10,4).

Crossrefs

See A094811 for another version.

Programs

Magma

I:=[6, 26, 100]; [n le 3 select I[n] else 6*Self(n-1)-10*Self(n-2)+4*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jun 08 2013

Maple

a:=k->sum(binomial(6+2*k,8*j+k-2),j=ceil((2-k)/8)..floor((8+k)/8))-sum(binomial(6+2*k,8*j+k-1),j=ceil((1-k)/8)..floor((7+k)/8)): seq(a(k),k=1..28);
A005022:=-1/((2*z-1)*(2*z**2-4*z+1)) -1; # [Conjectured (correctly) by Simon Plouffe in his 1992 dissertation. Gives sequence with an additional leading term of 1.]

Mathematica

CoefficientList[Series[-(2 (2 z^2 - 5 z + 3))/(4 z^3 - 10 z^2 + 6 z - 1), {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jun 27 2011 *)
CoefficientList[Series[(1 / x) (1 / (1 - 6 x + 10 x^2 - 4 x^3) - 1), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 08 2013 *)

PARI

Vec(2*(1-x)*(3-2*x) / ((1-2*x)*(1-4*x+2*x^2)) + O(x^50)) \\ Colin Barker, Apr 27 2016

Formula

G.f.: 1/(1-6x+10x^2-4x^3)-1.

a(n) = 6*a(n-1)-10*a(n-2)+4*a(n-3). - Emeric Deutsch, Apr 02 2004

a(k) = sum(binomial(6+2*k, 8*j+k-2)-binomial(6+2*k, 8*j+k-1), j=-infinity..infinity) (a finite sum).

The g.f. x^3/(1-6*x+10*x^2-4*x^3) occurs on page 320 of Viennot, 2002.

a(n) = -2^(1+n)+(3/2-sqrt(2))*(2-sqrt(2))^n+(3/2+sqrt(2))*(2+sqrt(2))^n - Colin Barker, Apr 27 2016

E.g.f.: (-2 + 3*cosh(sqrt(2)*x) + 2*sqrt(2)*sinh(sqrt(2)*x))*exp(2*x) - 1. - Ilya Gutkovskiy, Apr 27 2016

Extensions

Edited by Emeric Deutsch, Apr 28 2004