login
A349594
Number of 2 X n mazes that can be navigated from the top left corner to the bottom right corner.
4
1, 7, 40, 216, 1144, 6016, 31552, 165312, 865792, 4533760, 23739904, 124305408, 650874880, 3408031744, 17844699136, 93436084224, 489237741568, 2561682178048, 13413142233088, 70232124948480, 367740181282816, 1925512588951552, 10082114810675200, 52790638512439296
OFFSET
1,2
COMMENTS
a(n)/2^(3*n-2) is the probability that the top left and bottom right vertices of the 2 X n grid graph (or ladder graph) are still connected after each edge has been independently deleted with probability 1/2. - Pontus von Brömssen, May 25 2024
FORMULA
G.f.: (1 - x)/((1 - 2*x)*(1 - 6*x + 4*x^2)). - Andrew Howroyd, Nov 22 2021
EXAMPLE
For n = 2 the a(2) = 7 solutions are as follows:
+---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+
| | | | | | | | | | | | | | | |
+ + + + + + + +---+ + + + +---+ + +---+ + + +---+
| | | | | | | | | | | | | | | |
+---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+
MAPLE
a:= n-> (<<0|1|0>, <0|0|1>, <8|-16|8>>^n. <<0, 1, 7>>)[1, 1]:
seq(a(n), n=1..24); # Alois P. Heinz, Dec 09 2021
PROG
(PARI) Vec((1 - x)/((1 - 2*x)*(1 - 6*x + 4*x^2)) + O(x^30)) \\ Andrew Howroyd, Nov 22 2021
(Haskell)
import Data.List
m = [[2, 0, 2], [0, 2, 2], [1, 1, 4]]
(.*.) :: Num a => [[a]] -> [[a]] -> [[a]]
(.*.) a b = [[ sum $ zipWith (*) ar bc | bc <- (transpose b)] | ar <- a ]
(.^.) :: Num a => [[a]] -> Integer -> [[a]]
m .^. 0 = [ [ if i == j then 1 else 0 | i <- [1 .. n] ] | j <- [1 .. n] ] where n = length m
m .^. n | even n = let m' = m .^. (n `div` 2) in m' .*. m'
| otherwise = m .*. (m .^. (n - 1))
a349594 n = (z !! 0 !! 1) + (z !! 0 !! 2) + (z !! 2 !! 1) + (z !! 2 !! 2) where z = m .^. (n - 1)
CROSSREFS
Cf. A349596.
Second row/column of A373036.
Sequence in context: A351529 A081039 A227748 * A083327 A026716 A026782
KEYWORD
nonn,easy
AUTHOR
Eugene Nonko, Nov 22 2021
EXTENSIONS
Terms a(18) and beyond from Andrew Howroyd, Nov 22 2021
STATUS
approved