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,2

Links

Table of n, a(n) for n=1..24.

Eugene Nonko, Description of the problem and the approach to calculation

Eugene Nonko, C program to calculate

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

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.

Sequence in context: A351529 A081039 A227748 * A083327 A026716 A026782

Adjacent sequences: A349591 A349592 A349593 * A349595 A349596 A349597

Keyword

nonn,easy

Author

Eugene Nonko, Nov 22 2021

Extensions

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

Status

approved