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

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.

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

Crossrefs

Cf. A349594, A349596.

Fourth row/column of A373036.

Sequence in context: A229408 A269285 A133052 * A078204 A230466 A201248

Adjacent sequences: A365626 A365627 A365628 * A365630 A365631 A365632

Keyword

nonn,easy

Author

Eugene Nonko, Oct 25 2023

Extensions

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

Status

approved