A349594 Number of 2 X n mazes that can be navigated from the top left corner to the bottom right corner.

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

Author

Eugene Nonko, Nov 22 2021

Keywords

• nonn
• easy

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

Examples

			For n = 2 the a(2) = 7 solutions are as follows:
+---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
|       |   |   |   |   |       |   |       |   |       |   |       |   |   |   |
+   +   +   +   +   +   +   +---+   +   +   +   +---+   +   +---+   +   +   +---+
|       |   |       |   |       |   |   |   |   |       |   |   |   |   |       |
+---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
		

Links

• Index entries for linear recurrences with constant coefficients, signature (8,-16,8).

Crossrefs

Cf. A349596.

Second row/column of A373036.

Programs

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)

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

Mathematica

LinearRecurrence[{8, -16, 8}, {1, 7, 40}, 24] (* Jean-François Alcover, Jan 29 2025 *)

PARI

Vec((1 - x)/((1 - 2*x)*(1 - 6*x + 4*x^2)) + O(x^30)) \\ Andrew Howroyd, Nov 22 2021

Formula

G.f.: (1 - x)/((1 - 2*x)*(1 - 6*x + 4*x^2)). - Andrew Howroyd, Nov 22 2021

a(n) = ((5-3*sqrt(5))*(3-sqrt(5))^n + (5+3*sqrt(5))*(3+sqrt(5))^n - 10*2^n) / 40. - Eugene Nonko, Nov 07 2024

Extensions

Terms a(18) and beyond from Andrew Howroyd, Nov 22 2021