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

%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