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

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,1

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).

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

Example

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

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 *)

Prog

(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
(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

Crossrefs

See A094811 for another version.

Sequence in context: A344504 A261064 A094811 * A125107 A301476 A290347

Adjacent sequences: A005019 A005020 A005021 * A005023 A005024 A005025

Keyword

nonn,walk,easy

Author

N. J. A. Sloane, Simon Plouffe

Extensions

Edited by Emeric Deutsch, Apr 28 2004

Status

approved