|
| |
|
|
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
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. 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]
|
|
|
FORMULA
|
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
|
|
|
|
KEYWORD
|
nonn,walk,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
