cp's OEIS Frontend

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

%I A365629 #44 Jul 15 2025 10:23:51
%S A365629 1,216,28942,3329245,358911148,37502829018,3856945416544,
%T A365629 393396697543644,39951066751274152,4047887027105625168,
%U A365629 409638762069161924728,41428094401248851559736,4188336537335577744595384,423360539638841208001947048,42789587016771330584001089176
%N A365629 Number of 4 X n mazes that can be navigated from the top left corner to the bottom right corner.
%C A365629 If the maze can be navigated in multiple ways, it is still only counted once.
%C A365629 Sample 4 X 3 maze that can be navigated from the top left corner to the bottom right corner:
%C A365629   +---+---+---+---+
%C A365629   | S---+     |   |
%C A365629   +---+ | +---+   +
%C A365629   |     +---+ |   |
%C A365629   +   +---+ | +---+
%C A365629   |       | +---F |
%C A365629   +---+---+---+---+
%C A365629 Sample 4 X 3 maze that cannot be navigated from the top left corner to the bottom right corner:
%C A365629   +---+---+---+---+
%C A365629   | S             |
%C A365629   +---+   +---+   +
%C A365629   |       |   |   |
%C A365629   +   +---+   +---+
%C A365629   |   |         F |
%C A365629   +---+---+---+---+
%C A365629 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 A365629 Pontus von Brömssen, <a href="/A365629/b365629.txt">Table of n, a(n) for n = 1..499</a>
%H A365629 Eugene Nonko, <a href="https://github.com/eugene1729/cs/tree/main/maze">Description of the problem and the approach to calculation</a>.
%H A365629 Eugene Nonko, <a href="https://github.com/eugene1729/cs/blob/main/maze/maze.c">C program</a>.
%H A365629 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 A365629 <a href="/index/Rec#order_26">Index entries for linear recurrences with constant coefficients</a>, order 26.
%F A365629 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 A365629 Cf. A349594, A349596.
%Y A365629 Fourth row/column of A373036.
%K A365629 nonn,easy
%O A365629 1,2
%A A365629 _Eugene Nonko_, Oct 25 2023
%E A365629 a(8) and beyond from _Pontus von Brömssen_, May 25 2024