cp's OEIS Frontend

A204091 The number of 1 X n Haunted Mirror Maze puzzles with a unique solution ending with a mirror.

%I A204091 #36 Mar 25 2023 07:22:23
%S A204091 1,2,10,46,210,958,4370,19934,90930,414782,1892050,8630686,39369330,
%T A204091 179585278,819187730,3736768094,17045465010,77753788862,354678014290,
%U A204091 1617882493726,7380056440050,33664517212798,153562473183890,700483331493854,3195291711101490
%N A204091 The number of 1 X n Haunted Mirror Maze puzzles with a unique solution ending with a mirror.
%C A204091 The final slot can refer to a mirror of either type ('/' or '\'.)
%C A204091 A204092 counts the situation dropping the requirement that a board ends with a mirror. A204089 counts the situation where all mirrors have the same orientation. A204090 counts the boards with same orientation where the last square need not be a mirror.
%H A204091 Vincenzo Librandi, <a href="/A204091/b204091.txt">Table of n, a(n) for n = 0..1000</a>
%H A204091 Samples of these types of puzzles can be found at <a href="http://thegriddle.net/tags/haunted">this site</a>.
%H A204091 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (5,-2).
%F A204091 a(n) = 5*a(n-1) - 2*a(n-2) with a(1) = 2, a(2) = 10.
%F A204091 a(n) = 2 * sum_{i=0}^{i=n-1} a(n)(2^(n-i)-1), a(0) = 1.
%F A204091 G.f.: (1-x)*(1-2*x) / (1-5*x+2*x^2).
%F A204091 a(n) = (2^(1-n) * ((5+sqrt(17))^n - (5-sqrt(17))^n))/sqrt(17) for n>0. - _Colin Barker_, Nov 26 2016
%e A204091 For n=2 we get the following ten boards:
%e A204091 ('Z', '/')
%e A204091 ('Z', '|')
%e A204091 ('V', '/')
%e A204091 ('V', '|')
%e A204091 ('G', '/')
%e A204091 ('G', '|')
%e A204091 ('/', '/')
%e A204091 ('/', '|')
%e A204091 ('|', '/')
%e A204091 ('|', '|')
%t A204091 Join[{1}, LinearRecurrence[{5, -2}, {2, 10}, 40]]
%o A204091 (Python)
%o A204091 def a(n, d={0:1,1:2,2:10}):
%o A204091   if n in d:
%o A204091     return d[n]
%o A204091   d[n]=5*a(n-1) - 2*a(n-2)
%o A204091   return d[n]
%o A204091 for n in range(25):
%o A204091   print(a(n), end=', ')
%o A204091 (Python)
%o A204091 from itertools import product
%o A204091 def Lprint(n):
%o A204091     print("The following generate boards with a unique solution")
%o A204091     s = 0
%o A204091     for x in product(["Z", "V", "G", "/", "|"], repeat=n):
%o A204091         if x[-1] == "/" or x[-1] == "|":
%o A204091             y = list(x) # Splitting x up into a list pieces
%o A204091             z = list()
%o A204091             while y:
%o A204091                 if "/" in y or "|" in y:
%o A204091                     if "/" in y and "|" in y:
%o A204091                         m = min(y.index("/"), y.index("|"))
%o A204091                     else:
%o A204091                         if "/" in y:
%o A204091                             m = y.index("/")
%o A204091                         else:
%o A204091                             m = y.index("|")
%o A204091                     if y[0] not in ["/", "|"]:
%o A204091                         z.append(y[:m])
%o A204091                     y = y[m + 1 :]
%o A204091                 else:
%o A204091                     z.append(y)
%o A204091                     y = []
%o A204091             goodword = True
%o A204091             for w in z: # For each element in the list checking for Z&V together
%o A204091                 if "Z" in w and "V" in w:
%o A204091                     goodword = False
%o A204091             if goodword:
%o A204091                 s += 1
%o A204091                 print(x)
%o A204091     return s
%o A204091 print(Lprint(5))
%o A204091 (PARI) Vec((1-x)*(1-2*x)/(1-5*x+2*x^2) + O(x^30)) \\ _Colin Barker_, Nov 26 2016
%Y A204091 Cf. A204089-A204092.
%Y A204091 Apart from signs and the initial term, same as A106709.
%K A204091 nonn,easy
%O A204091 0,2
%A A204091 _David Nacin_, Jan 10 2012