|
%I #29 Sep 16 2018 21:16:09
%S 1,2,8,34,134,498,1786,6274,21778,75074,257762,882946,3020354,
%T 10323714,35270530,120467458,411394306,1404773378,4796567042,
%U 16377245698,55916897282,190915194882,651831179266,2225502715906,7598365282306,25942489251842,88573293551618
%N The number of 1 X n Haunted Mirror Maze puzzles with a unique solution where mirror orientation is fixed.
%C 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 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 Vincenzo Librandi, <a href="/A204090/b204090.txt">Table of n, a(n) for n = 0..1000</a>
%H Samples of these types of puzzles can be found at <a href="http://thegriddle.net/tags/haunted">this</a> and other sites.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (7,-16,14,-4).
%F G.f.: (1 - 5*x + 10*x^2 - 4*x^3) / ((1 - x)*(1 - 2*x)*(1 - 4*x + 2*x^2)).
%F a(n) = A204089(n+1) - 2^(n+1) + 2.
%F 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 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 For n=3 we would get the following 34 boards with unique solutions:
%e ('Z', 'Z', '/')
%e ('Z', 'G', '/')
%e ('Z', '/', 'Z')
%e ('Z', '/', 'V')
%e ('Z', '/', 'G')
%e ('Z', '/', '/')
%e ('V', 'V', '/')
%e ('V', 'G', '/')
%e ('V', '/', 'Z')
%e ('V', '/', 'V')
%e ('V', '/', 'G')
%e ('V', '/', '/')
%e ('G', 'Z', '/')
%e ('G', 'V', '/')
%e ('G', 'G', 'G')
%e ('G', 'G', '/')
%e ('G', '/', 'Z')
%e ('G', '/', 'V')
%e ('G', '/', 'G')
%e ('G', '/', '/')
%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[{7, -16, 14, -4}, {1, 2, 8, 34}, 40]
%o (Python)
%o def a(n, d={0:1,1:2,2:8,3:34}):
%o .if n in d:
%o ..return d[n]
%o .d[n]=7*a(n-1) - 16*a(n-2) + 14*a(n-3) - 4*a(n-4)
%o .return d[n]
%o (Python)
%o #Produces a(n) through enumeration and also displays boards:
%o def Hprint(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 ..#Taking care of the no mirror case
%o ..if '/' not in x:
%o ...if 'Z' not in x and 'V' not in x:
%o ....s+=1
%o ....print(x)
%o ..else:
%o ...#Splitting x up into a list pieces
%o ...y=list(x)
%o ...z=list()
%o ...while 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-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 Cf. A204089, A204091, A204092.
%K nonn,easy
%O 0,2
%A _David Nacin_, Jan 10 2012
|
