cp's OEIS Frontend

A204089 The number of 1 by n Haunted Mirror Maze puzzles with a unique solution ending with a mirror, where mirror orientation is fixed.

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