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

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

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

A206306 Riordan array (1, x/(1-3x+2x^2)).

Original entry on oeis.org

1, 0, 1, 0, 3, 1, 0, 7, 6, 1, 0, 15, 23, 9, 1, 0, 31, 72, 48, 12, 1, 0, 63, 201, 198, 82, 15, 1, 0, 127, 522, 699, 420, 125, 18, 1, 0, 255, 1291, 2223, 1795, 765, 177, 21, 1, 0, 511, 3084, 6562, 6768, 3840, 1260, 238, 24, 1

Offset: 0

Philippe Deléham, Feb 06 2012

The convolution triangle of the Mersenne numbers A000225. - Peter Luschny, Oct 09 2022

			Triangle begins:
  1;
  0,    1;
  0,    3,    1;
  0,    7,    6,     1;
  0,   15,   23,     9,     1;
  0,   31,   72,    48,    12,     1;
  0,   63,  201,   198,    82,    15,    1;
  0,  127,  522,   699,   420,   125,   18,    1;
  0,  255, 1291,  2223,  1795,   765,  177,   21,   1;
  0,  511, 3084,  6562,  6768,  3840, 1260,  238,  24,  1;
  0, 1023, 7181, 18324, 23276, 16758, 7266, 1932, 308, 27,  1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Columns: A000007, A000225 (Mersenne numbers), A045618, A055582.
Cf. A008585, A009545, A084938, A062725, A110441, A204089, A204091.
Cf. A045741, A078020, A244038.

function T(n,k) // T = A206306
  if k lt 0 or k gt n then return 0;
  elif k eq n then return 1;
  elif k eq 0 then return 0;
  else return 3*T(n-1, k) +T(n-1, k-1) -2*T(n-2, k);
  end if; return T;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Dec 20 2022

# Uses function PMatrix from A357368.
PMatrix(10, n -> 2^n - 1); # Peter Luschny, Oct 09 2022

T[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[k==n, 1, If[k==0, 0, 3*T[n- 1, k] +T[n-1, k-1] -2*T[n-2, k]]]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Dec 20 2022 *)

def T(n,k): # T = A206306
    if (k<0 or k>n): return 0
    elif (k==n): return 1
    elif (k==0): return 0
    else: return 3*T(n-1, k) +T(n-1, k-1) -2*T(n-2, k)
flatten([[T(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Dec 20 2022

Triangle T(n,k), read by rows, given by (0, 3, -2/3, 2/3, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (1, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938.
Diagonals sums are even-indexed Fibonacci numbers.
Sum_{k=0..n} T(n,k)*x^k = A000007(n), A204089(n), A204091(n) for x = 0, 1, 2 respectively.
G.f.: (1-3*x+2*x^)/(1-(3+y)*x+2*x^2).
From Philippe Deléham, Nov 17 2013; corrected Feb 13 2020: (Start)
T(n, n) = 1.
T(n+1, n) = 3n = A008585(n).
T(n+2, n) = A062725(n).
T(n,k) = 3*T(n-1,k)+T(n-1,k-1)-2*T(n-2,k), T(0,0)=T(1,1)=T(2,2)=1, T(1,0)=T(2,0)=0, T(2,1)=3, T(n,k)=0 if k<0 or if k>n. (End)
From G. C. Greubel, Dec 20 2022: (Start)
Sum_{k=0..n} (-1)^k*T(n,k) = [n=1] - A009545(n).
Sum_{k=0..n} (-2)^k*T(n,k) = [n=1] + A078020(n+1).
T(2*n, n+1) = A045741(n+2), n >= 0.
T(2*n+1, n+1) = A244038(n). (End)

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

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

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

A206306 Riordan array (1, x/(1-3*x+2*x^2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A206306 Riordan array (1, x/(1-3x+2x^2)).