A005025 Random walks.

9, 53, 260, 1156, 4845, 19551, 76912, 297275, 1134705, 4292145, 16128061, 60304951, 224660626, 834641671, 3094322026, 11453607152, 42344301686, 156404021389, 577291806894, 2129654436910, 7853149169635, 28949515515376, 106692395098433, 393137817645838

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• walk
• easy

Comments

Number of walks of length 2n+9 in the path graph P_10 from one end to the other one. - 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]
• 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
• Index entries for linear recurrences with constant coefficients, signature (9,-28,35,-15,1).

Programs

Magma

I:=[9,53,260,1156,4845]; [n le 5 select I[n] else 9*Self(n-1)-28*Self(n-2)+35*Self(n-3)-15*Self(n-4)+Self(n-5): n in [1..30]]; // Vincenzo Librandi, Jun 20 2017

Maple

a:=k->sum(binomial(9+2*k,11*j+k-2),j=ceil((2-k)/11)..floor((11+k)/11))-sum(binomial(9+2*k,11*j+k-1),j=ceil((1-k)/11)..floor((10+k)/11)): seq(a(k),k=1..28);
A005025:=-(9-28*z+35*z**2-15*z**3+z**4)/(-1+9*z-28*z**2+35*z**3-15*z**4+z**5); # Simon Plouffe in his 1992 dissertation

Mathematica

LinearRecurrence[{9, -28, 35, -15, 1}, {9, 53, 260, 1156, 4845}, 25] (* Vincenzo Librandi, Jun 20 2017 *)

Formula

From Emeric Deutsch, Apr 02 2004: (Start)

G.f.: 1/(1 - 9*x + 28*x^2 - 35*x^3 + 15*x^4 - x^5) - 1.

a(n) = 9*a(n-1) - 28*a(n-2) + 35*a(n-3) - 15*a(n-4) + a(n-5). (End)

a(k) = Sum_{j=-infinity..infinity} (binomial(9+2*k, 11j+k-2) - binomial(9+2*k, 11j+k-1)) (a finite sum).