A204091 The number of 1 X n Haunted Mirror Maze puzzles with a unique solution ending with a mirror.

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

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]
for n in range(25):
  print(a(n), end=', ')
(Python)
from itertools import product
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] == "|":
            y = list(x) # Splitting x up into a list pieces
            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 ["/", "|"]:
                        z.append(y[:m])
                    y = y[m + 1 :]
                else:
                    z.append(y)
                    y = []
            goodword = True
            for w in z: # For each element in the list checking for Z&V together
                if "Z" in w and "V" in w:
                    goodword = False
            if goodword:
                s += 1
                print(x)
    return s
print(Lprint(5))
(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.

Apart from signs and the initial term, same as A106709.

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