login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005021 Random walks (binomial transform of A006054).
(Formerly M3888)
19
1, 5, 19, 66, 221, 728, 2380, 7753, 25213, 81927, 266110, 864201, 2806272, 9112264, 29587889, 96072133, 311945595, 1012883066, 3288813893, 10678716664, 34673583028, 112584429049, 365559363741, 1186963827439, 3854047383798, 12514013318097, 40632746115136 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Number of walks of length 2n+5 in the path graph P_6 from one end to the other one. Example: a(1)=5 because in the path ABCDEF we have ABABCDEF, ABCBCDEF, ABCDCDEF, ABCDEDEF and ABCDEFEF. - Emeric Deutsch, Apr 02 2004

Since a(n) is the binomial transform of A006054 from formula (3.63) in the Witula-Slota-Warzynski paper, it follows that a(n)=A(n;1)*(B(n;-1)-C(n;-1))-B(n;1)*B(n;-1)+C(n;1)*(A(n;-1)-B(n;-1)+C(n;-1)), where A(n;1)=A077998(n), B(n;1)=A006054(n+1), C(n;1)=A006054(n), A(n;-1)=A121449(n), B(n+1;-1)=-A085810(n+1), C(n;-1)=A215404(n) and A(n;d), B(n;d), C(n;d), n in N, d in C, denote the quasi-Fibonacci numbers defined and discussed in comments in A121449 and in the cited paper. - Roman Witula, Aug 09 2012

From Wolfdieter Lang, Mar 30 2020: (Start)

With offset -4 this sequence 6, 1, 0, 0, 1, 5, ... appears in the formula for the n-th power of the 3 X 3 tridiagonal Matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602: (M_3)^n = a(n-2)*(M_3)^2 - (6*a(n-3) - a(n-4))*M_3 + a(n-3)*1_3, with the 3 X 3 unit matrix 1_3, for n >= 0. Proof from Cayley-Hamilton: (M_3)^n = 5*(M_3)^3 - 6*M_3 + 1_3 (see A332602 for the characteristic polynomial Phi(3, x)), and the recurrence (M_3)^n = M_3*(M_3)^(n-1). For (M_3)^n[1,1] = 2*a(n-2) - 5*a(n-3) + a(n-4), for n >= 0, see A080937(n).

The formula for a(n) in terms of r = rho(7) = A160389 given below shows that a(n)/a(n-1) converges to rho(7)^2 = A116425 = 3.2469796... for n -> infinity. This is because r - 2/r = 0.692..., and r - 1 - 1/r = 0.137... .

(End)

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

G. C. Greubel, Table of n, a(n) for n = 0..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]

G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]

S. Morier-Genoud, V. Ovsienko and S. Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, Annales de l'institut Fourier, 62 no. 3 (2012), 937-987; arXiv:1008.3359 [math.AG], 2010-2011. - From N. J. A. Sloane, Dec 26 2012

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

N. J. A. Sloane, Transforms

Roman Witula, Damian Slota and Adam Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq., 9 (2006), Article 06.4.3.

Index entries for linear recurrences with constant coefficients, signature (5,-6,1).

FORMULA

G.f.: 1/(1-5x+6x^2-x^3). - Emeric Deutsch, Apr 02 2004

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

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

a(n-2) = 2^n*C(n;1/2)=(1/7)*((c(2)-c(4))*(c(4))^(2n) + (c(4)-c(1))*(c(1))^(2n) + (c(1)-c(2))*(c(2))^(2n)), where a(-2)=a(-1):=0, c(j):=2*cos(2Pi*j/7). This formula follows from the Binet formula for C(n;d)--one of the quasi-Fibonacci numbers (see comments in A121449 and the formula (3.17) in the Witula-Slota-Warzynski paper). - Roman Witula, Aug 09 2012

In terms of the algebraic number r = rho(7) = 2*cos(Pi/7) = A160389 of degree 3 the preceding formula gives a(n) = r^(2*(n+2))*(A1(r) + A2(r)*(r - 2/r)^(2*(n+1)) = A3(r)*(r - 1 - 1/r)^(2*(n+1)))/7, for n >= -4 (see a comment above for this offset), with A1(r) = -r^2 + 2*r + 1, A2(r) = -r^2 - r + 2, and A3(r) = 2*r^2 - r - 3. - Wolfdieter Lang, Mar 30 2020

MAPLE

a:=k->sum(binomial(5+2*k, 7*j+k-2), j=ceil((2-k)/7)..floor((7+k)/7))-sum(binomial(5+2*k, 7*j+k-1), j=ceil((1-k)/7)..floor((6+k)/7)): seq(a(k), k=0..25);

A005021:=-(z-1)*(z-5)/(-1+5*z-6*z**2+z**3); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence apart from the initial 1

MATHEMATICA

LinearRecurrence[{5, -6, 1}, {1, 5, 19}, 50] (* Roman Witula, Aug 09 2012 *)

CoefficientList[Series[1/(1 - 5 x + 6 x^2 - x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)

PROG

(MAGMA) I:=[1, 5, 19]; [n le 3 select I[n] else 5*Self(n-1)-6*Self(n-2)+Self(n-3): n in [1..30]]; // Vincenzo Librandi, Sep 18 2015

(PARI) x='x+O('x^30); Vec(1/(1-5*x+6*x^2-x^3)) \\ G. C. Greubel, Apr 19 2018

CROSSREFS

Double partial sums of A060557. Bisection of A052547.

Cf. A094789, A094790, A080937, A160389, A116425, A322602.

Sequence in context: A124806 A059509 A137745 * A067325 A273599 A121525

Adjacent sequences:  A005018 A005019 A005020 * A005022 A005023 A005024

KEYWORD

nonn,walk,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

a(25)-a(26) from Vincenzo Librandi, Sep 18 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 1 13:20 EDT 2020. Contains 334762 sequences. (Running on oeis4.)