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

1, 2, 8, 34, 134, 498, 1786, 6274, 21778, 75074, 257762, 882946, 3020354, 10323714, 35270530, 120467458, 411394306, 1404773378, 4796567042, 16377245698, 55916897282, 190915194882, 651831179266, 2225502715906, 7598365282306, 25942489251842, 88573293551618

Offset

0,2

Comments

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.

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.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Samples of these types of puzzles can be found at this and other sites.

Index entries for linear recurrences with constant coefficients, signature (7,-16,14,-4).

Formula

G.f.: (1 - 5*x + 10*x^2 - 4*x^3) / ((1 - x)*(1 - 2*x)*(1 - 4*x + 2*x^2)).

a(n) = A204089(n+1) - 2^(n+1) + 2.

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.

a(n) = 2 - 2^(1+n) + ((2+sqrt(2))^(1+n) - (2-sqrt(2))^(1+n))/(2*sqrt(2)). - Colin Barker, Nov 26 2016

Example

For n=3 we would get the following 34 boards with unique solutions:
('Z', 'Z', '/')
('Z', 'G', '/')
('Z', '/', 'Z')
('Z', '/', 'V')
('Z', '/', 'G')
('Z', '/', '/')
('V', 'V', '/')
('V', 'G', '/')
('V', '/', 'Z')
('V', '/', 'V')
('V', '/', 'G')
('V', '/', '/')
('G', 'Z', '/')
('G', 'V', '/')
('G', 'G', 'G')
('G', 'G', '/')
('G', '/', 'Z')
('G', '/', 'V')
('G', '/', 'G')
('G', '/', '/')
('/', 'Z', 'Z')
('/', 'Z', 'G')
('/', 'Z', '/')
('/', 'V', 'V')
('/', 'V', 'G')
('/', 'V', '/')
('/', 'G', 'Z')
('/', 'G', 'V')
('/', 'G', 'G')
('/', 'G', '/')
('/', '/', 'Z')
('/', '/', 'V')
('/', '/', 'G')
('/', '/', '/')

Mathematica

LinearRecurrence[{7, -16, 14, -4}, {1, 2, 8, 34}, 40]

Prog

(Python)
def a(n, d={0:1, 1:2, 2:8, 3:34}):
.if n in d:
..return d[n]
.d[n]=7*a(n-1) - 16*a(n-2) + 14*a(n-3) - 4*a(n-4)
.return d[n]
(Python)
#Produces a(n) through enumeration and also displays boards:
def Hprint(n):
.print('The following generate boards with a unique solution')
.s=0
.for x in product(['Z', 'V', 'G', '/'], repeat=n):
..#Taking care of the no mirror case
..if '/' not in x:
...if 'Z' not in x and 'V' not in x:
....s+=1
....print(x)
..else:
...#Splitting x up into a list pieces
...y=list(x)
...z=list()
...while y:
....if '/' in y:
.....if y[0] != '/': #Don't need to add blank pieces to z
......z.append(y[:y.index('/')])
.....y=y[y.index('/')+1:]
....else:
.....z.append(y)
.....y=[]
...#For each element in the list checking for Z&V together
...goodword=True
...for w in z:
....if 'Z' in w and 'V' in w:
.....goodword=False
...if goodword:
....s+=1
....print(x)
.return s
(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

Crossrefs

Cf. A204089, A204091, A204092.

Sequence in context: A172448 A268601 A026577 * A226495 A111643 A000163

Adjacent sequences: A204087 A204088 A204089 * A204091 A204092 A204093

Keyword

nonn,easy

Author

David Nacin, Jan 10 2012

Status

approved