A204089 - OEIS

%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