cp's OEIS Frontend

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

%I A349594 #33 Jan 29 2025 11:18:57
%S A349594 1,7,40,216,1144,6016,31552,165312,865792,4533760,23739904,124305408,
%T A349594 650874880,3408031744,17844699136,93436084224,489237741568,
%U A349594 2561682178048,13413142233088,70232124948480,367740181282816,1925512588951552,10082114810675200,52790638512439296
%N A349594 Number of 2 X n mazes that can be navigated from the top left corner to the bottom right corner.
%C A349594 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
%H A349594 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (8,-16,8).
%F A349594 G.f.: (1 - x)/((1 - 2*x)*(1 - 6*x + 4*x^2)). - _Andrew Howroyd_, Nov 22 2021
%F A349594 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
%e A349594 For n = 2 the a(2) = 7 solutions are as follows:
%e A349594 +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
%e A349594 |       |   |   |   |   |       |   |       |   |       |   |       |   |   |   |
%e A349594 +   +   +   +   +   +   +   +---+   +   +   +   +---+   +   +---+   +   +   +---+
%e A349594 |       |   |       |   |       |   |   |   |   |       |   |   |   |   |       |
%e A349594 +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
%p A349594 a:= n-> (<<0|1|0>, <0|0|1>, <8|-16|8>>^n. <<0, 1, 7>>)[1, 1]:
%p A349594 seq(a(n), n=1..24);  # _Alois P. Heinz_, Dec 09 2021
%t A349594 LinearRecurrence[{8, -16, 8}, {1, 7, 40}, 24] (* _Jean-François Alcover_, Jan 29 2025 *)
%o A349594 (PARI) Vec((1 - x)/((1 - 2*x)*(1 - 6*x + 4*x^2)) + O(x^30)) \\ _Andrew Howroyd_, Nov 22 2021
%o A349594 (Haskell)
%o A349594 import Data.List
%o A349594 m = [[2, 0, 2], [0, 2, 2], [1, 1, 4]]
%o A349594 (.*.) :: Num a => [[a]] -> [[a]] -> [[a]]
%o A349594 (.*.) a b = [[ sum $ zipWith (*) ar bc | bc <- (transpose b)] | ar <- a ]
%o A349594 (.^.) :: Num a => [[a]] -> Integer -> [[a]]
%o A349594 m .^. 0 = [ [ if i == j then 1 else 0 | i <- [1 .. n] ] | j <- [1 .. n] ] where n = length m
%o A349594 m .^. n | even n = let m' = m .^. (n `div` 2) in m' .*. m'
%o A349594         | otherwise = m .*. (m .^. (n - 1))
%o A349594 a349594 n = (z !! 0 !! 1) + (z !! 0 !! 2) + (z !! 2 !! 1) + (z !! 2 !! 2) where z = m .^. (n - 1)
%Y A349594 Cf. A349596.
%Y A349594 Second row/column of A373036.
%K A349594 nonn,easy
%O A349594 1,2
%A A349594 _Eugene Nonko_, Nov 22 2021
%E A349594 Terms a(18) and beyond from _Andrew Howroyd_, Nov 22 2021