The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
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!)
A068912 Number of n step walks (each step +/-1 starting from 0) which are never more than 3 or less than -3. 6
1, 2, 4, 8, 14, 28, 48, 96, 164, 328, 560, 1120, 1912, 3824, 6528, 13056, 22288, 44576, 76096, 152192, 259808, 519616, 887040, 1774080, 3028544, 6057088, 10340096, 20680192, 35303296, 70606592, 120532992, 241065984, 411525376, 823050752, 1405035520, 2810071040 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
The number of n step walks (each step +/-1 starting from 0) which are never more than k or less than -k is given by a(n,k) = 2^n/(k+1)*Sum_{r=1..k+1} (-1)^r*cos((Pi*(2*r-1))/(2*(k+1)))^n*cot((Pi*(1-2*r))/(4*(k+1))). Here we have k=3. - Herbert Kociemba, Sep 19 2020
LINKS
T. Mansour and A. O. Munagi, Alternating subsets modulo m, Rocky Mt. J. Math. 42, No. 4, 1313-1325 (2012), Table 1 q=(0,1,1,1).
FORMULA
G.f.: (1+2*x)/(1-4*x^2+2*x^4).
a(n) = A068913(3, n).
a(n) = 4*a(n-2) - 2*a(n-4).
a(2*n) = A007070(n) = 2*a(2*n-1)-A060995(n); a(2*n+1) = 2*a(2*n).
a(n) = (2^n/4)*Sum_{r=1..4} (-1)^r*cos((Pi*(2*r-1))/8)^n*cot((Pi*(1-2*r))/16). - Herbert Kociemba, Sep 19 2020
Conjecture: a(n) = floor((1+r)^(n/2)*(r+(2*(1+r))^(1/2)+(-1)^n*(r-(2*(1+r))^(1/2)))/4) where r = 1 + 2^(1/2). - Peter Luschny, Sep 20 2020
From Herbert Kociemba, Sep 20 2020: (Start)
With the standard procedure to obtain an explicit formula for a(n) for a linear recurrence and r1=2-sqrt(2) and r2=2+sqrt(2) we get
a(n) = a1(n) + a2(n) with
a1(n) = -(r1^(n/2)*(-2*(-1+(-1)^n)*sqrt(r1)+(1+(-1)^n)*r1))/(4*sqrt(2)) and
a2(n) = +(r2^(n/2)*(-2*(-1+(-1)^n)*sqrt(r2)+(1+(-1)^n)*r2))/(4*sqrt(2)).
We have -1<a1(n)<0 for all n, so a(n)= floor(a2(n)). (End)
MAPLE
# From Peter Luschny, Sep 20 2020: (Start)
r := 1 + 2^(1/2): s := 1 - 2^(1/2):
c := n -> (1+r)^(n/2)*(r+(2*(1+r))^(1/2)+(-1)^n*(r-(2*(1+r))^(1/2))):
b := n -> (1+s)^(n/2)*(s-(2*(1+s))^(1/2)+(-1)^n*(s+(2*(1+s))^(1/2))):
a := n -> (c(n) + b(n))/4:
# Alternatively:
a := proc(n) local h; h := n -> add((1+x)*(2+x)^(n/2), x=[sqrt(2), -sqrt(2)]);
if n::even then h(n)/2 else h(n-1) fi end:
seq(simplify(a(n)), n=0..30); # (End)
MATHEMATICA
nn=33; CoefficientList[Series[s+a + b + c + d + e +f/.Solve[{s ==1 + x a + x b, a==x s + x c, b==x s +x d, c==x a +x e, d== x b + x f, e==x c, f==x d, z==x e + x f }, {s, a, b, c, d, e, f, z}], {x, 0, nn}], x] (* Geoffrey Critzer, Jan 13 2014 *)
a[n_, k_]:=2^n /(k+1) Sum[(-1)^r Cos[(Pi (2r-1))/(2 (k+1))]^n Cot[(Pi (1-2r))/(4 (k+1))] , {r, 1, k+1}]
Table[a[n, 3], {n, 0, 40}]//Round (* Herbert Kociemba, Sep 19 2020 *)
a[n_]:=Module[{r=2+Sqrt[2]}, Floor[(r^(n/2) (-2 (-1+(-1)^n) Sqrt[r]+(1+(-1)^n) r))/(4 Sqrt[2])]]
Table[a[n], {n, 0, 40}] (* Herbert Kociemba, Sep 21 2020 *)
CROSSREFS
Cf. A000007, A016116 (without initial term), A068911, A068913 for similar.
Sequence in context: A196721 A118034 A096590 * A164176 A325860 A217932
KEYWORD
nonn,walk,easy
AUTHOR
Henry Bottomley, Mar 06 2002
STATUS
approved

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 May 30 14:34 EDT 2024. Contains 372968 sequences. (Running on oeis4.)