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

1, 216, 28942, 3329245, 358911148, 37502829018, 3856945416544, 393396697543644, 39951066751274152, 4047887027105625168, 409638762069161924728, 41428094401248851559736, 4188336537335577744595384, 423360539638841208001947048, 42789587016771330584001089176

Offset: 1

Author

Eugene Nonko, Oct 25 2023

Keywords

• nonn
• easy

Comments

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

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

+---+---+---+---+

| S---+ | |

+---+ | +---+ +

| +---+ | |

+ +---+ | +---+

| | +---F |

+---+---+---+---+

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

+---+---+---+---+

| S |

+---+ +---+ +

| | | |

+ +---+ +---+

| | F |

+---+---+---+---+

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

Links

• Pontus von Brömssen, Table of n, a(n) for n = 1..499
• Eugene Nonko, Description of the problem and the approach to calculation.
• Eugene Nonko, C program.
• Steven B. Segletes, On the Electrical Connectivity of a 2-D, Randomly Distributed, Two-Component (Conducting/Insulating) Mixture, Devcom, ARL-TR-8899, Jan 2020; page 15 lists a(4).
• Index entries for linear recurrences with constant coefficients, order 26.

Crossrefs

Cf. A349594, A349596.

Fourth row/column of A373036.

Formula

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

Extensions

a(8) and beyond from Pontus von Brömssen, May 25 2024