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

%I #38 Oct 04 2024 10:00:15

%S 1,216,28942,3329245,358911148,37502829018,3856945416544,

%T 393396697543644,39951066751274152,4047887027105625168,

%U 409638762069161924728,41428094401248851559736,4188336537335577744595384,423360539638841208001947048,42789587016771330584001089176

%N Number of 4 X n mazes that can be navigated from the top left corner to the bottom right corner.

%C If the maze can be navigated in multiple ways, it is still only counted once.

%C Sample 4 X 3 maze that can be navigated from the top left corner to the bottom right corner:

%C +---+---+---+---+

%C | S---+ | |

%C +---+ | +---+ +

%C | +---+ | |

%C + +---+ | +---+

%C | | +---F |

%C +---+---+---+---+

%C Sample 4 X 3 maze that cannot be navigated from the top left corner to the bottom right corner:

%C +---+---+---+---+

%C | S |

%C +---+ +---+ +

%C | | | |

%C + +---+ +---+

%C | | F |

%C +---+---+---+---+

%C a(n)/2^(7*n-4) is the probability that the top left and bottom right vertices of the 4 X n grid graph are still connected after each edge has been independently deleted with probability 1/2. - _Pontus von Brömssen_, May 25 2024

%H Pontus von Brömssen, <a href="/A365629/b365629.txt">Table of n, a(n) for n = 1..499</a>

%H Eugene Nonko, <a href="https://github.com/eugene1729/cs/tree/main/maze">Description of the problem and the approach to calculation</a>.

%H Eugene Nonko, <a href="https://github.com/eugene1729/cs/blob/main/maze/maze.c">C program</a>.

%H Steven B. Segletes, <a href="https://apps.dtic.mil/sti/citations/AD1090614">On the Electrical Connectivity of a 2-D, Randomly Distributed, Two-Component (Conducting/Insulating) Mixture</a>, Devcom, ARL-TR-8899, Jan 2020; page 15 lists a(4).

%H <a href="/index/Rec#order_26">Index entries for linear recurrences with constant coefficients</a>, order 26.

%F a(n) = 342*a(n-1) - 50227*a(n-2) + 4267092*a(n-3) - 237414878*a(n-4) + 9263866752*a(n-5) - 264710439296*a(n-6) + 5705797123488*a(n-7) - 94777393717760*a(n-8) + 1232582325433344*a(n-9) - 12699878523256832*a(n-10) + 104584257652924416*a(n-11) - 692664147070386176*a(n-12) + 3704337209642582016*a(n-13) - 16028068661845557248*a(n-14) + 56107328210955927552*a(n-15) - 158569903559869988864*a(n-16) + 360259507824309043200*a(n-17) - 653476498517472051200*a(n-18) + 937026705910470279168*a(n-19) - 1047482862825245769728*a(n-20) + 895397884025628524544*a(n-21) - 569457883581280944128*a(n-22) + 258763464527314944000*a(n-23) - 78758950283455234048*a(n-24) + 14267403619509731328*a(n-25) - 1152921504606846976*a(n-26) for n >= 27. - _Pontus von Brömssen_, May 25 2024

%Y Cf. A349594, A349596.

%Y Fourth row/column of A373036.

%K nonn,easy

%O 1,2

%A _Eugene Nonko_, Oct 25 2023

%E a(8) and beyond from _Pontus von Brömssen_, May 25 2024