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

Comments

Apart from a leading 1, the same as A007070. - R. J. Mathar, Jan 16 2012

Since the uniqueness of a solution is unaffected by the orientation of the mirrors in this 1 by n case, we assume mirror orientation is fixed for this sequence.

Dropping the requirement that the board end with a mirror gives A204090. Allowing for mirror orientation gives A204091. Allowing for orientation and dropping the requirement gives A204092.

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

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

Example

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', '/')
('/', '/', '/')

Mathematica

LinearRecurrence[{4, -2}, {1, 1, 4}, 31]

Prog

(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
(PARI) Vec((1-x)*(1-2*x)/(1-4*x+2*x^2) + O(x^30)) \\ Michel Marcus, Dec 06 2015
(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
(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

Crossrefs

Cf. A007070, A204090, A204091, A204092.

Sequence in context: A127359 A289928 A007070 * A092489 A094827 A094667

Adjacent sequences: A204086 A204087 A204088 * A204090 A204091 A204092

Keyword

nonn,easy

Author

David Nacin, Jan 10 2012

Status

approved