OFFSET
0,3
COMMENTS
Apart from a leading 1, the same as A007070. - R. J. Mathar, Jan 16 2012
Since the uniqueness of a solution is unaffected by the orientation of the mirrors in this 1 by n case, we assume mirror orientation is fixed for this sequence.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
David Millar, Haunted Puzzles, The Griddle.
Index entries for linear recurrences with constant coefficients, signature (4,-2).
FORMULA
G.f.: (1-x)*(1-2*x)/(1-4*x+2*x^2).
a(n) = Sum_{i=0..n-1} a(i) * (2^(n-i)-1), with a(0)=1.
a(n) = 4*a(n-1) - 2*a(n-2), a(1)=1, a(2)=4.
G.f.: (1-x)*(1-2*x)/(1 - 4*x + 2*x^2) = 1/(1 + U(0)) where U(k)= 1 - 2^k/(1 - x/(x - 2^k/U(k+1) )); (continued fraction 3rd kind, 3-step). - Sergei N. Gladkovskii, Dec 05 2012
a(n) = ((2+sqrt(2))^n - (2-sqrt(2))^n)/(2*sqrt(2)). - Colin Barker, Dec 06 2015
a(n) = [n=0] + 2^((n-1)/2)*ChebyshevU(n-1, sqrt(2)). - G. C. Greubel, Dec 21 2022
E.g.f.: 1 + exp(2*x)*sinh(sqrt(2)*x)/sqrt(2). - Stefano Spezia, May 20 2024
EXAMPLE
For M(3) we would have the following possibilities:
('Z', 'Z', '/')
('Z', 'G', '/')
('Z', '/', '/')
('V', 'V', '/')
('V', 'G', '/')
('V', '/', '/')
('G', 'Z', '/')
('G', 'V', '/')
('G', 'G', '/')
('G', '/', '/')
('/', 'Z', '/')
('/', 'V', '/')
('/', 'G', '/')
('/', '/', '/')
MATHEMATICA
LinearRecurrence[{4, -2}, {1, 1, 4}, 31]
PROG
(Python)
def a(n, d={0:1, 1:4}):
if n in d: return d[n]
d[n] = 4*a(n-1) - 2*a(n-2)
return d[n]
print([1]+[a(n) for n in range(31)])
(Python)
#Produces a(n) through enumeration and also displays boards:
def Mprint(n):
.print('The following generate boards with a unique solution')
.s=0
.for x in product(['Z', 'V', 'G', '/'], repeat=n):
..if x[-1]=='/':
...#Splitting x up into a list pieces
...y=list(x)
...z=list()
...while y:
....#print(y)
....if '/' in y:
.....if y[0] != '/': #Don't need to add blank pieces to z
......z.append(y[:y.index('/')])
.....y=y[y.index('/')+1:]
....else:
.....z.append(y)
.....y=[]
...#For each element in the list checking for Z&V together
...goodword=True
...for w in z:
....if 'Z' in w and 'V' in w:
.....goodword=False
...if goodword:
....s+=1
....print(x)
.return s
(PARI) Vec((1-x)*(1-2*x)/(1-4*x+2*x^2) + O(x^30)) \\ Michel Marcus, Dec 06 2015
(Magma) [1] cat [n le 2 select 4^(n-1) else 4*Self(n-1) - 2*Self(n-2): n in [1..30]]; // G. C. Greubel, Dec 21 2022
(SageMath)
def A204089(n): return int(n==0) + 2^((n-1)/2)*chebyshev_U(n-1, sqrt(2))
[A204089(n) for n in range(31)] # G. C. Greubel, Dec 21 2022
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
David Nacin, Jan 10 2012
STATUS
approved