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.
This sequence (beginning at 4) is the same as the size of bets in pot limit poker, maximum raising, with small blind 1 and big blind 1. Setting a(0) = 1 and a(1) = 1, the pot limit bet facing player n>=2 is a(n)=3*a(n-1)+ Sum_{k=0..n-2} a(k). (Poker dealers calculate this easily as: 3 times the last bet plus the shrapnel). This leads to the recurrence relation a(n) = 4*a(n-1)-2*a(n-2) for n>=2. - Patrick Butler, Dec 18 2025
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
E.g.f.: 1 + exp(2*x)*sinh(sqrt(2)*x)/sqrt(2). - Stefano Spezia, May 20 2024
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
KEYWORD
nonn,easy
AUTHOR
David Nacin, Jan 10 2012
STATUS
approved