OFFSET
0,2
COMMENTS
The final slot can refer to a mirror of either type ('/' or '\'.)
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
KEYWORD
nonn,easy
AUTHOR
David Nacin, Jan 10 2012
STATUS
approved