A204089 The number of 1 by n Haunted Mirror Maze puzzles with a unique solution ending with a mirror, where mirror orientation is fixed.
1, 1, 4, 14, 48, 164, 560, 1912, 6528, 22288, 76096, 259808, 887040, 3028544, 10340096, 35303296, 120532992, 411525376, 1405035520, 4797091328, 16378294272, 55918994432, 190919389184, 651839567872, 2225519493120, 7598398836736, 25942556360704, 88573427769344
Offset: 0
Examples
For M(3) we would have the following possibilities:
('Z', 'Z', '/')
('Z', 'G', '/')
('Z', '/', '/')
('V', 'V', '/')
('V', 'G', '/')
('V', '/', '/')
('G', 'Z', '/')
('G', 'V', '/')
('G', 'G', '/')
('G', '/', '/')
('/', 'Z', '/')
('/', 'V', '/')
('/', 'G', '/')
('/', '/', '/')
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..1000
- David Millar, Haunted Puzzles, The Griddle.
- Index entries for linear recurrences with constant coefficients, signature (4,-2).
Programs
-
Magma
[1] cat [n le 2 select 4^(n-1) else 4*Self(n-1) - 2*Self(n-2): n in [1..30]]; // G. C. Greubel, Dec 21 2022
-
Mathematica
LinearRecurrence[{4,-2}, {1,1,4}, 31] -
PARI
Vec((1-x)*(1-2*x)/(1-4*x+2*x^2) + O(x^30)) \\ Michel Marcus, Dec 06 2015
-
Python
def a(n, d={0:1, 1:4}): if n in d: return d[n] d[n] = 4*a(n-1) - 2*a(n-2) return d[n] print([1]+[a(n) for n in range(31)]) -
Python
#Produces a(n) through enumeration and also displays boards: def Mprint(n): print('The following generate boards with a unique solution') s=0 for x in product(['Z', 'V', 'G', '/'], repeat=n): if x[-1]=='/': #Splitting x up into a list pieces y=list(x) z=list() while y: #print(y) if '/' in y: if y[0] != '/': #Don't need to add blank pieces to z z.append(y[:y.index('/')]) y=y[y.index('/')+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 -
SageMath
def A204089(n): return int(n==0) + 2^((n-1)/2)*chebyshev_U(n-1, sqrt(2)) [A204089(n) for n in range(31)] # G. C. Greubel, Dec 21 2022
Formula
G.f.: (1-x)*(1-2*x)/(1-4*x+2*x^2).
a(n) = Sum_{i=0..n-1} a(i) * (2^(n-i)-1), with a(0)=1.
a(n) = 4*a(n-1) - 2*a(n-2), a(1)=1, a(2)=4.
G.f.: (1-x)*(1-2*x)/(1 - 4*x + 2*x^2) = 1/(1 + U(0)) where U(k)= 1 - 2^k/(1 - x/(x - 2^k/U(k+1) )); (continued fraction 3rd kind, 3-step). - Sergei N. Gladkovskii, Dec 05 2012
a(n) = ((2+sqrt(2))^n - (2-sqrt(2))^n)/(2*sqrt(2)). - Colin Barker, Dec 06 2015
a(n) = [n=0] + 2^((n-1)/2)*ChebyshevU(n-1, sqrt(2)). - G. C. Greubel, Dec 21 2022
E.g.f.: 1 + exp(2*x)*sinh(sqrt(2)*x)/sqrt(2). - Stefano Spezia, May 20 2024
Comments