login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A204091 The number of 1 X n Haunted Mirror Maze puzzles with a unique solution ending with a mirror. 5
1, 2, 10, 46, 210, 958, 4370, 19934, 90930, 414782, 1892050, 8630686, 39369330, 179585278, 819187730, 3736768094, 17045465010, 77753788862, 354678014290, 1617882493726, 7380056440050, 33664517212798, 153562473183890, 700483331493854, 3195291711101490 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

The final slot can refer to a mirror of either type ('/' or '\'.)

A204092 counts the situation dropping the requirement that a board ends with a mirror. A204089 counts the situation where all mirrors have the same orientation. A204090 counts the boards with same orientation where the last square need not be a mirror.

LINKS

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

Samples of these types of puzzles can be found at this site.

Index entries for linear recurrences with constant coefficients, signature (5,-2).

FORMULA

a(n) = 5*a(n-1) - 2*a(n-2) with a(1) = 2, a(2) = 10.

a(n) = 2 * sum_{i=0}^{i=n-1} a(n)(2^(n-i)-1), a(0) = 1.

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

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

EXAMPLE

For n=2 we get the following ten boards:

('Z', '/')

('Z', '|')

('V', '/')

('V', '|')

('G', '/')

('G', '|')

('/', '/')

('/', '|')

('|', '/')

('|', '|')

MATHEMATICA

Join[{1}, LinearRecurrence[{5, -2}, {2, 10}, 40]]

PROG

(Python)

def a(n, d={0:1, 1:2, 2:10}):

if n in d:

return d[n]

d[n]=5*a(n-1) - 2*a(n-2)

return d[n]

(Python)

#Produces a(n) through enumeration and also displays boards::

def Lprint(n):

.print('The following generate boards with a unique solution')

.s=0

.for x in product(['Z', 'V', 'G', '/', '|'], repeat=n):

..if x[-1]=='/' or x[-1]=='|':

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

(PARI) Vec((1-x)*(1-2*x)/(1-5*x+2*x^2) + O(x^30)) \\ Colin Barker, Nov 26 2016

CROSSREFS

Cf. A204089-A204092.

Sequence in context: A032389 A290923 A106709 * A221196 A137193 A006213

Adjacent sequences:  A204088 A204089 A204090 * A204092 A204093 A204094

KEYWORD

nonn,easy

AUTHOR

David Nacin, Jan 10 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 25 03:49 EST 2020. Contains 331241 sequences. (Running on oeis4.)