A204090 -id:A204090 - cp's OEIS frontend

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

David Nacin, Jan 10 2012

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.

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

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

Cf. A007070, A204090, A204091, A204092.

[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]
```

Vec((1-x)*(1-2*x)/(1-4*x+2*x^2) + O(x^30)) \\ Michel Marcus, Dec 06 2015

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

#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

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

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

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

Original entry on oeis.org

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

David Nacin, Jan 10 2012

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.

			For n=2 we get the following ten boards:
('Z', '/')
('Z', '|')
('V', '/')
('V', '|')
('G', '/')
('G', '|')
('/', '/')
('/', '|')
('|', '/')
('|', '|')

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

Cf. A204089-A204092.

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

Join[{1}, LinearRecurrence[{5, -2}, {2, 10}, 40]]

Vec((1-x)*(1-2*x)/(1-5*x+2*x^2) + O(x^30)) \\ Colin Barker, Nov 26 2016

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=', ')

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

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

A204092 The number of 1 by n Haunted Mirror Maze puzzles with a unique solution.

Original entry on oeis.org

1, 3, 17, 91, 449, 2123, 9841, 45211, 206881, 945003, 4313297, 19680571, 89784449, 409577483, 1868351281, 8522666971, 38876763361, 177338745003, 808940722577, 3690027171451, 16832256509249, 76781232397643, 350241657358321, 1597645838773531, 7287745912705441

Offset: 0

David Nacin, Jan 10 2012

Requiring the last slot contain a mirror results in A204091. Fixing orientation of mirrors results in A204090. Fixing orientation and requiring the last slot be a mirror results in A204089.

			The following 17 boards illustrate K(2):
('Z', '/')
('Z', '|')
('V', '/')
('V', '|')
('G', 'G')
('G', '/')
('G', '|')
('/', 'Z')
('/', 'V')
('/', 'G')
('/', '/')
('/', '|')
('|', 'Z')
('|', 'V')
('|', 'G')
('|', '/')
('|', '|')

Samples of these types of puzzles can be found at this site.
Index entries for linear recurrences with constant coefficients, signature (8,-19,16,-4).

Cf. A204089, A204090, A204091.

LinearRecurrence[{8, -19, 16, -4}, {1, 3, 17, 91}, 40]

def a(n, d={0:1,1:3,2:17,3:91}):
 if n in d:
  return d[n]
 d[n]=8*a(n-1) - 19*a(n-2) + 16*a(n-3) - 4*a(n-4)
 return d[n]

#Produces a(n) through enumeration and also displays boards:
def Kprint(n):
 print('The following generate boards with a unique solution')
 s=0
 for x in product(['Z','V','G','/','|'],repeat=n):
  #Taking care of the no mirror case
  if '/' not in x and '|' not in x:
   if 'Z' not in x and 'V' not in x:
    s+=1
    print(x)
  else:
   #Splitting x up into a list pieces
   y=list(x)
   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 ['/','|']: #Don't need to add blank pieces to z
      z.append(y[:m])
     y=y[m+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

a(n) = A204091(n+1)/2 - 2^(n+1) + 2.
a(n) = 8*a(n-1) - 19*a(n-2) + 16*a(n-3) - 4*a(n-4), a(0) = 1, a(1) = 3, a(2) = 17, a(3) = 91.
G.f.: (1-5x+12x^2-4x^3)/((1-x)(1-2x)(1-5x+2x^2)).

cp's OEIS Frontend

A204089 The number of 1 by n Haunted Mirror Maze puzzles with a unique solution ending with a mirror, where mirror orientation is fixed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Python

SageMath

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Formula

A204092 The number of 1 by n Haunted Mirror Maze puzzles with a unique solution.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Python

Formula