login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005021 Random walks (binomial transform of A006054).
(Formerly M3888)
19

%I M3888 #86 Sep 08 2022 08:44:33

%S 1,5,19,66,221,728,2380,7753,25213,81927,266110,864201,2806272,

%T 9112264,29587889,96072133,311945595,1012883066,3288813893,

%U 10678716664,34673583028,112584429049,365559363741,1186963827439,3854047383798,12514013318097,40632746115136

%N Random walks (binomial transform of A006054).

%C 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

%C 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

%C From _Wolfdieter Lang_, Mar 30 2020: (Start)

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

%C 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... .

%C (End)

%D W. Feller, An Introduction to Probability Theory and its Applications, 3rd ed, Wiley, New York, 1968, p. 96.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H G. C. Greubel, <a href="/A005021/b005021.txt">Table of n, a(n) for n = 0..1000</a>

%H Jean-Luc Baril and Helmut Prodinger, <a href="https://arxiv.org/abs/2205.01383">Enumeration of partial Lukasiewicz paths</a>, arXiv:2205.01383 [math.CO], 2022.

%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.

%H Nachum Dershowitz, <a href="https://arxiv.org/abs/2006.06516">Between Broadway and the Hudson: A Bijection of Corridor Paths</a>, arXiv:2006.06516 [math.CO], 2020.

%H C. J. Everett, P. R. Stein, <a href="http://dx.doi.org/10.1016/0012-365X(77)90019-X">The combinatorics of random walk with absorbing barriers</a>, Discrete Math. 17 (1977), no. 1, 27-45.

%H C. J. Everett, P. R. Stein, <a href="/A005021/a005021.pdf">The combinatorics of random walk with absorbing barriers</a>, Discrete Math. 17 (1977), no. 1, 27-45. [Annotated scanned copy]

%H G. Kreweras, <a href="/A000108/a000108_1.pdf">Sur les éventails de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]

%H S. Morier-Genoud, V. Ovsienko and S. Tabachnikov, <a href="http://arxiv.org/abs/1008.3359">2-frieze patterns and the cluster structure of the space of polygons</a>, 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

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H László Németh and László Szalay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Nemeth/nemeth8.html">Sequences Involving Square Zig-Zag Shapes</a>, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.

%H Roman Witula, Damian Slota and Adam Warzynski, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Slota/slota57.html">Quasi-Fibonacci Numbers of the Seventh Order</a>, J. Integer Seq., 9 (2006), Article 06.4.3.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-6,1).

%F G.f.: 1/(1-5x+6x^2-x^3). - _Emeric Deutsch_, Apr 02 2004

%F a(n) = 5*a(n-1) -6*a(n-2) +a(n-3). - _Emeric Deutsch_, Apr 02 2004

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

%F 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

%F 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

%p 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);

%p 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

%t LinearRecurrence[{5,-6,1}, {1,5,19}, 50] (* _Roman Witula_, Aug 09 2012 *)

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

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

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

%Y Double partial sums of A060557. Bisection of A052547.

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

%K nonn,walk,easy

%O 0,2

%A _N. J. A. Sloane_

%E a(25)-a(26) from _Vincenzo Librandi_, Sep 18 2015

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 08:48 EDT 2024. Contains 371268 sequences. (Running on oeis4.)