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,2

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.

Links

Table of n, a(n) for n=0..24.

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

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

Example

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

Mathematica

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

Prog

(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

Crossrefs

Cf. A204089, A204090, A204091.

Sequence in context: A203851 A198766 A240652 * A221731 A290925 A020056

Adjacent sequences: A204089 A204090 A204091 * A204093 A204094 A204095

Keyword

nonn,easy

Author

David Nacin, Jan 10 2012

Status

approved