%I #54 May 21 2024 01:24:38
%S 1,1,4,14,48,164,560,1912,6528,22288,76096,259808,887040,3028544,
%T 10340096,35303296,120532992,411525376,1405035520,4797091328,
%U 16378294272,55918994432,190919389184,651839567872,2225519493120,7598398836736,25942556360704,88573427769344
%N The number of 1 by n Haunted Mirror Maze puzzles with a unique solution ending with a mirror, where mirror orientation is fixed.
%C Apart from a leading 1, the same as A007070. - _R. J. Mathar_, Jan 16 2012
%C 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.
%C Dropping the requirement that the board end with a mirror gives A204090. Allowing for mirror orientation gives A204091. Allowing for orientation and dropping the requirement gives A204092.
%H Vincenzo Librandi, <a href="/A204089/b204089.txt">Table of n, a(n) for n = 0..1000</a>
%H David Millar, <a href="http://thegriddle.net/tags/haunted">Haunted Puzzles</a>, The Griddle.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2).
%F G.f.: (1-x)*(1-2*x)/(1-4*x+2*x^2).
%F a(n) = Sum_{i=0..n-1} a(i) * (2^(n-i)-1), with a(0)=1.
%F a(n) = 4*a(n-1) - 2*a(n-2), a(1)=1, a(2)=4.
%F 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
%F a(n) = ((2+sqrt(2))^n - (2-sqrt(2))^n)/(2*sqrt(2)). - _Colin Barker_, Dec 06 2015
%F a(n) = [n=0] + 2^((n-1)/2)*ChebyshevU(n-1, sqrt(2)). - _G. C. Greubel_, Dec 21 2022
%F E.g.f.: 1 + exp(2*x)*sinh(sqrt(2)*x)/sqrt(2). - _Stefano Spezia_, May 20 2024
%e For M(3) we would have the following possibilities:
%e ('Z', 'Z', '/')
%e ('Z', 'G', '/')
%e ('Z', '/', '/')
%e ('V', 'V', '/')
%e ('V', 'G', '/')
%e ('V', '/', '/')
%e ('G', 'Z', '/')
%e ('G', 'V', '/')
%e ('G', 'G', '/')
%e ('G', '/', '/')
%e ('/', 'Z', '/')
%e ('/', 'V', '/')
%e ('/', 'G', '/')
%e ('/', '/', '/')
%t LinearRecurrence[{4,-2}, {1,1,4}, 31]
%o (Python)
%o def a(n, d={0:1, 1:4}):
%o if n in d: return d[n]
%o d[n] = 4*a(n-1) - 2*a(n-2)
%o return d[n]
%o print([1]+[a(n) for n in range(31)])
%o (Python)
%o #Produces a(n) through enumeration and also displays boards:
%o def Mprint(n):
%o .print('The following generate boards with a unique solution')
%o .s=0
%o .for x in product(['Z', 'V', 'G', '/'], repeat=n):
%o ..if x[-1]=='/':
%o ...#Splitting x up into a list pieces
%o ...y=list(x)
%o ...z=list()
%o ...while y:
%o ....#print(y)
%o ....if '/' in y:
%o .....if y[0] != '/': #Don't need to add blank pieces to z
%o ......z.append(y[:y.index('/')])
%o .....y=y[y.index('/')+1:]
%o ....else:
%o .....z.append(y)
%o .....y=[]
%o ...#For each element in the list checking for Z&V together
%o ...goodword=True
%o ...for w in z:
%o ....if 'Z' in w and 'V' in w:
%o .....goodword=False
%o ...if goodword:
%o ....s+=1
%o ....print(x)
%o .return s
%o (PARI) Vec((1-x)*(1-2*x)/(1-4*x+2*x^2) + O(x^30)) \\ _Michel Marcus_, Dec 06 2015
%o (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
%o (SageMath)
%o def A204089(n): return int(n==0) + 2^((n-1)/2)*chebyshev_U(n-1, sqrt(2))
%o [A204089(n) for n in range(31)] # _G. C. Greubel_, Dec 21 2022
%Y Cf. A007070, A204090, A204091, A204092.
%K nonn,easy
%O 0,3
%A _David Nacin_, Jan 10 2012