|
|
A135318
|
|
The Kentucky-2 sequence: a(n) = a(n-2) + 2*a(n-4), with a[0..3] = [1, 1, 1, 2].
|
|
5
|
|
|
1, 1, 1, 2, 3, 4, 5, 8, 11, 16, 21, 32, 43, 64, 85, 128, 171, 256, 341, 512, 683, 1024, 1365, 2048, 2731, 4096, 5461, 8192, 10923, 16384, 21845, 32768, 43691, 65536, 87381, 131072, 174763, 262144, 349525, 524288, 699051, 1048576, 1398101, 2097152, 2796203
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Shifted Jacobsthal recurrence.
Let U be the unit-primitive matrix (see [Jeffery])
U=U_(6,2)=
(0 0 1)
(0 2 0)
(2 0 1),
let i in {0,1}, m>=0 an integer and n=2*m+i. Then a(n)=a(2*m+i)=Sum_{j=0..2} (U^m)_(i,j). (End)
a(n) is also the pebbling number of the cycle graph C_{n+1} for n > 1. - Eric W. Weisstein, Jan 07 2021
a(n) is the number of ways to tile a zig-zag strip of n cells using squares (of 1 cell) and triangles (of 3 cells). Here is the zig-zag strip corresponding to n=11, with 11 cells:
___ ___
___| |___| |___
| |___| |___| |___
|___| |___| |___| |
| |___| |___| |___|
|___| |___| |___|,
and here are the two types of triangles (where one is just a reflection of the other):
___ ___
| |___ ___| |
| | | |
| ___| and |___ |
|___| |___|.
As an example, here is one of the a(11) = 32 ways to tile the zig-zag strip of 11 cells:
___ ___
___| |___| |___
| |___| | |___
| |___ | |
| ___| |___| ___|
|___| |___| |___|. (End)
|
|
LINKS
|
|
|
FORMULA
|
O.g.f.: [1/(1+x^2)+(-2-3*x)/(2*x^2-1)]/3.
G.f.: (1+x+x^3)/((1+x^2)*(1-2*x^2)).
a(n) = (((-i)^(n+1)-i^(n+1))*2*i*sqrt(2)+3*(1+(-1)^(n+1))*2^((n+2)/2)+(1-(-1)^(n+1))*2^((n+5)/2))/(12*sqrt(2)), where i=sqrt(-1). (End)
|
|
EXAMPLE
|
Let i=0 and m=3. Then U^3 = (2,0,3;0,8,0;6,0,5), and the first-row sum (corresponding to i=0) is 2 + 0 + 3 = 5. Hence a(n) = a(2*m+i) = a(2*3+0) = a(6) = 2 + 3 = 5.
|
|
MAPLE
|
a:= n-> (<<0|1>, <2|1>>^(iquo(n, 2, 'm')). <<1, 1+m>>)[1, 1]:
|
|
MATHEMATICA
|
LinearRecurrence[{0, 1, 0, 2}, {1, 1, 1, 2}, 40] (* Harvey P. Dale, Oct 14 2015 *)
|
|
PROG
|
(Magma) [(2^Floor(n/2)*(5-(-1)^n)+(-1)^Floor(n/2)*(1+(-1)^n))/6: n in [0..50]]; // Vincenzo Librandi, Aug 10 2011
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|