cp's OEIS Frontend

A204090 The number of 1 X n Haunted Mirror Maze puzzles with a unique solution where mirror orientation is fixed.

%I A204090 #31 May 22 2025 10:21:35
%S A204090 1,2,8,34,134,498,1786,6274,21778,75074,257762,882946,3020354,
%T A204090 10323714,35270530,120467458,411394306,1404773378,4796567042,
%U A204090 16377245698,55916897282,190915194882,651831179266,2225502715906,7598365282306,25942489251842,88573293551618
%N A204090 The number of 1 X n Haunted Mirror Maze puzzles with a unique solution where mirror orientation is fixed.
%C A204090 Since the uniqueness of a solution is unaffected by the orientation of the mirrors in this 1 X n case, we assume mirror orientation is fixed for this sequence.
%C A204090 Connected to A204089, which counts the 1 X n boards with unique solutions that end in a mirror. Dropping the mirror orientation restriction would give A204092. Dropping the orientation restriction and requiring a mirror in the last slot gives A204091.
%H A204090 Vincenzo Librandi, <a href="/A204090/b204090.txt">Table of n, a(n) for n = 0..1000</a>
%H A204090 Samples of these types of puzzles can be found at <a href="http://thegriddle.net/tags/haunted">this</a> and other sites.
%H A204090 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (7,-16,14,-4).
%F A204090 G.f.: (1 - 5*x + 10*x^2 - 4*x^3) / ((1 - x)*(1 - 2*x)*(1 - 4*x + 2*x^2)).
%F A204090 a(n) = A204089(n+1) - 2^(n+1) + 2.
%F A204090 a(n) = 7*a(n-1) - 16*a(n-2) + 14*a(n-3) - 4*a(n-4), a(0)=1, a(1)=2, a(2)=8, a(3)=34.
%F A204090 a(n) = 2 - 2^(1+n) + ((2+sqrt(2))^(1+n) - (2-sqrt(2))^(1+n))/(2*sqrt(2)). - _Colin Barker_, Nov 26 2016
%e A204090 For n=3 we would get the following 34 boards with unique solutions:
%e A204090 ('Z', 'Z', '/')
%e A204090 ('Z', 'G', '/')
%e A204090 ('Z', '/', 'Z')
%e A204090 ('Z', '/', 'V')
%e A204090 ('Z', '/', 'G')
%e A204090 ('Z', '/', '/')
%e A204090 ('V', 'V', '/')
%e A204090 ('V', 'G', '/')
%e A204090 ('V', '/', 'Z')
%e A204090 ('V', '/', 'V')
%e A204090 ('V', '/', 'G')
%e A204090 ('V', '/', '/')
%e A204090 ('G', 'Z', '/')
%e A204090 ('G', 'V', '/')
%e A204090 ('G', 'G', 'G')
%e A204090 ('G', 'G', '/')
%e A204090 ('G', '/', 'Z')
%e A204090 ('G', '/', 'V')
%e A204090 ('G', '/', 'G')
%e A204090 ('G', '/', '/')
%e A204090 ('/', 'Z', 'Z')
%e A204090 ('/', 'Z', 'G')
%e A204090 ('/', 'Z', '/')
%e A204090 ('/', 'V', 'V')
%e A204090 ('/', 'V', 'G')
%e A204090 ('/', 'V', '/')
%e A204090 ('/', 'G', 'Z')
%e A204090 ('/', 'G', 'V')
%e A204090 ('/', 'G', 'G')
%e A204090 ('/', 'G', '/')
%e A204090 ('/', '/', 'Z')
%e A204090 ('/', '/', 'V')
%e A204090 ('/', '/', 'G')
%e A204090 ('/', '/', '/')
%t A204090 LinearRecurrence[{7, -16, 14, -4}, {1, 2, 8, 34}, 40]
%o A204090 (Python)
%o A204090 def a(n, d={0:1,1:2,2:8,3:34}):
%o A204090  if n in d:
%o A204090   return d[n]
%o A204090  d[n]=7*a(n-1) - 16*a(n-2) + 14*a(n-3) - 4*a(n-4)
%o A204090  return d[n]
%o A204090 (Python)
%o A204090 #Produces a(n) through enumeration and also displays boards:
%o A204090 def Hprint(n):
%o A204090  print('The following generate boards with a unique solution')
%o A204090  s=0
%o A204090  for x in product(['Z','V','G','/'],repeat=n):
%o A204090   #Taking care of the no mirror case
%o A204090   if '/' not in x:
%o A204090    if 'Z' not in x and 'V' not in x:
%o A204090     s+=1
%o A204090     print(x)
%o A204090   else:
%o A204090    #Splitting x up into a list pieces
%o A204090    y=list(x)
%o A204090    z=list()
%o A204090    while y:
%o A204090     if '/' in y:
%o A204090      if y[0] != '/': #Don't need to add blank pieces to z
%o A204090       z.append(y[:y.index('/')])
%o A204090      y=y[y.index('/')+1:]
%o A204090     else:
%o A204090      z.append(y)
%o A204090      y=[]
%o A204090    #For each element in the list checking for Z&V together
%o A204090    goodword=True
%o A204090    for w in z:
%o A204090     if 'Z' in w and 'V' in w:
%o A204090      goodword=False
%o A204090    if goodword:
%o A204090     s+=1
%o A204090     print(x)
%o A204090  return s
%o A204090 (PARI) Vec((1-5*x+10*x^2-4*x^3) / ((1-x)*(1-2*x)*(1-4*x+2*x^2)) + O(x^30)) \\ _Colin Barker_, Nov 26 2016
%Y A204090 Cf. A204089, A204091, A204092.
%K A204090 nonn,easy
%O A204090 0,2
%A A204090 _David Nacin_, Jan 10 2012