A204092 -id:A204092 - 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

A204090 The number of 1 X n Haunted Mirror Maze puzzles with a unique solution where mirror orientation is fixed.

Original entry on oeis.org

1, 2, 8, 34, 134, 498, 1786, 6274, 21778, 75074, 257762, 882946, 3020354, 10323714, 35270530, 120467458, 411394306, 1404773378, 4796567042, 16377245698, 55916897282, 190915194882, 651831179266, 2225502715906, 7598365282306, 25942489251842, 88573293551618

Offset: 0

David Nacin, Jan 10 2012

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

Connected to A204089, which counts the 1 X n boards with unique solutions that end in a mirror. Dropping the mirror orientation restriction would give A204092. Dropping the orientation restriction and requiring a mirror in the last slot gives A204091.

			For n=3 we would get the following 34 boards with unique solutions:
('Z', 'Z', '/')
('Z', 'G', '/')
('Z', '/', 'Z')
('Z', '/', 'V')
('Z', '/', 'G')
('Z', '/', '/')
('V', 'V', '/')
('V', 'G', '/')
('V', '/', 'Z')
('V', '/', 'V')
('V', '/', 'G')
('V', '/', '/')
('G', 'Z', '/')
('G', 'V', '/')
('G', 'G', 'G')
('G', 'G', '/')
('G', '/', 'Z')
('G', '/', 'V')
('G', '/', 'G')
('G', '/', '/')
('/', '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
Samples of these types of puzzles can be found at this and other sites.
Index entries for linear recurrences with constant coefficients, signature (7,-16,14,-4).

Cf. A204089, A204091, A204092.

LinearRecurrence[{7, -16, 14, -4}, {1, 2, 8, 34}, 40]

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

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

#Produces a(n) through enumeration and also displays boards:
def Hprint(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:
   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:
     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

G.f.: (1 - 5*x + 10*x^2 - 4*x^3) / ((1 - x)*(1 - 2*x)*(1 - 4*x + 2*x^2)).
a(n) = A204089(n+1) - 2^(n+1) + 2.
a(n) = 7*a(n-1) - 16*a(n-2) + 14*a(n-3) - 4*a(n-4), a(0)=1, a(1)=2, a(2)=8, a(3)=34.
a(n) = 2 - 2^(1+n) + ((2+sqrt(2))^(1+n) - (2-sqrt(2))^(1+n))/(2*sqrt(2)). - Colin Barker, Nov 26 2016

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

A204090 The number of 1 X n Haunted Mirror Maze puzzles with a unique solution where mirror orientation is fixed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Formula