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

Author

David Nacin, Jan 10 2012

Keywords

• nonn
• easy

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.

Examples

			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')
('/', '/', '/')
		

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).

Crossrefs

Cf. A204089, A204091, A204092.

Programs

Mathematica

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

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

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

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