A204092 The number of 1 by n Haunted Mirror Maze puzzles with a unique solution.

1, 3, 17, 91, 449, 2123, 9841, 45211, 206881, 945003, 4313297, 19680571, 89784449, 409577483, 1868351281, 8522666971, 38876763361, 177338745003, 808940722577, 3690027171451, 16832256509249, 76781232397643, 350241657358321, 1597645838773531, 7287745912705441

Offset: 0

Author

David Nacin, Jan 10 2012

Keywords

• nonn
• easy

Comments

Requiring the last slot contain a mirror results in A204091. Fixing orientation of mirrors results in A204090. Fixing orientation and requiring the last slot be a mirror results in A204089.

Examples

			The following 17 boards illustrate K(2):
('Z', '/')
('Z', '|')
('V', '/')
('V', '|')
('G', 'G')
('G', '/')
('G', '|')
('/', 'Z')
('/', 'V')
('/', 'G')
('/', '/')
('/', '|')
('|', 'Z')
('|', 'V')
('|', 'G')
('|', '/')
('|', '|')
		

Links

• Samples of these types of puzzles can be found at this site.
• Index entries for linear recurrences with constant coefficients, signature (8,-19,16,-4).

Crossrefs

Cf. A204089, A204090, A204091.

Programs

Mathematica

LinearRecurrence[{8, -19, 16, -4}, {1, 3, 17, 91}, 40]

Python

def a(n, d={0:1,1:3,2:17,3:91}):
 if n in d:
  return d[n]
 d[n]=8*a(n-1) - 19*a(n-2) + 16*a(n-3) - 4*a(n-4)
 return d[n]

Python

#Produces a(n) through enumeration and also displays boards:
def Kprint(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 and '|' 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 or '|' in y:
     if '/' in y and '|' in y:
      m = min(y.index('/'), y.index('|'))
     else:
      if '/' in y:
       m=y.index('/')
      else:
       m=y.index('|')
     if y[0] not in ['/','|']: #Don't need to add blank pieces to z
      z.append(y[:m])
     y=y[m+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

a(n) = A204091(n+1)/2 - 2^(n+1) + 2.

a(n) = 8*a(n-1) - 19*a(n-2) + 16*a(n-3) - 4*a(n-4), a(0) = 1, a(1) = 3, a(2) = 17, a(3) = 91.

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