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

Author

David Nacin, Jan 10 2012

Keywords

• nonn
• easy

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.

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

Crossrefs

Cf. A007070, A204090, A204091, A204092.

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