Eugene Nonko - cp's OEIS frontend

User: Eugene Nonko

Eugene Nonko has authored 3 sequences.

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

Eugene Nonko, Oct 25 2023

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

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.

Cf. A349594, A349596.

Fourth row/column of A373036.

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

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

A349596 Number of edge subsets E of the 3 X n grid graph such that E contains a path between the top left node and the bottom right node.

Original entry on oeis.org

1, 40, 1135, 28942, 707239, 16963938, 403490839, 9560192914, 226115020735, 5343643837642, 126235739481031, 2981618243157330, 70418570359871599, 1663054542669694138, 39275207266744385815, 927528207559891996258, 21904544495171662611391, 517297785739589326153482

Offset: 1

Eugene Nonko, Nov 22 2021

a(n)/2^(5*n-3) is the probability that the top left and bottom right vertices of the 3 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

Pontus von Brömssen, Table of n, a(n) for n = 1..728
Steven B Segletes, On the Electrical Connectivity of a 2-D, Randomly Distributed, Two-Component (Conducting/Insulating) Mixture, page 12 lists number for 3 X 3 maze.
Index entries for linear recurrences with constant coefficients, signature (54,-1077,10642,-57954,180960,-324992,325632,-165888,32768).

Cf. A349594.

Third row/column of A373036.

a(n) = 54*a(n-1) - 1077*a(n-2) + 10642*a(n-3) - 57954*a(n-4) + 180960*a(n-5) - 324992*a(n-6) + 325632*a(n-7) - 165888*a(n-8) + 32768*a(n-9) for n >= 10. - Pontus von Brömssen, May 25 2024

G.f.: (1 - 14*x + 52*x^2 + 90*x^3 - 960*x^4 + 2096*x^5 - 1792*x^6 + 512*x^7)/((1 - 15*x + 48*x^2 - 32*x^3)*(1 - 39*x + 444*x^2 - 2078*x^3 + 4224*x^4 - 3648*x^5 + 1024*x^6)). - Eugene Nonko, Nov 15 2024

a(11)-a(18) from Martin Ehrenstein, Dec 13 2021

Name clarified by Eugene Nonko, Nov 18 2024

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

Original entry on oeis.org

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

Eugene Nonko, Nov 22 2021

a(n)/2^(3*n-2) is the probability that the top left and bottom right vertices of the 2 X n grid graph (or ladder graph) are still connected after each edge has been independently deleted with probability 1/2. - Pontus von Brömssen, May 25 2024

			For n = 2 the a(2) = 7 solutions are as follows:
+---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
|       |   |   |   |   |       |   |       |   |       |   |       |   |   |   |
+   +   +   +   +   +   +   +---+   +   +   +   +---+   +   +---+   +   +   +---+
|       |   |       |   |       |   |   |   |   |       |   |   |   |   |       |
+---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   +---+---+

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

Cf. A349596.

Second row/column of A373036.

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)

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

LinearRecurrence[{8, -16, 8}, {1, 7, 40}, 24] (* Jean-François Alcover, Jan 29 2025 *)

Vec((1 - x)/((1 - 2*x)*(1 - 6*x + 4*x^2)) + O(x^30)) \\ Andrew Howroyd, Nov 22 2021

G.f.: (1 - x)/((1 - 2*x)*(1 - 6*x + 4*x^2)). - Andrew Howroyd, Nov 22 2021

a(n) = ((5-3*sqrt(5))*(3-sqrt(5))^n + (5+3*sqrt(5))*(3+sqrt(5))^n - 10*2^n) / 40. - Eugene Nonko, Nov 07 2024

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

cp's OEIS Frontend

User: Eugene Nonko

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A349596 Number of edge subsets E of the 3 X n grid graph such that E contains a path between the top left node and the bottom right node.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions