A349594 -id:A349594 - cp's OEIS frontend

A373036 Triangle read by rows: T(n,k) is the number of edge subsets E of the n X k grid graph such that E contains a path between the top left node and the bottom right node, 1 <= k <= n.

1, 1, 7, 1, 40, 1135, 1, 216, 28942, 3329245, 1, 1144, 707239, 358911148, 167176484530, 1, 6016, 16963938, 37502829018, 74568672196498, 140386491543732211, 1, 31552, 403490839, 3856945416544, 32485805235240376, 256258754970108999490, 1946586793700869420041631

Offset: 1

Pontus von Brömssen, May 20 2024

T(n,k)/2^A151890(n-1,k-1) is the probability that the top left and bottom right vertices of the n X k grid graph are still connected after each edge has been independently deleted with probability 1/2.

Terms in the n-th row/column satisfies a linear recurrence with constant coefficients (probably of order A000245(n) or less).

			Triangle begins:
  1;
  1,    7;
  1,   40,     1135;
  1,  216,    28942,     3329245;
  1, 1144,   707239,   358911148,   167176484530;
  1, 6016, 16963938, 37502829018, 74568672196498, 140386491543732211;
  ...

Eugene Nonko, Table of n, a(n) for n = 1..105 (rows 1..14, terms 1..55 from Pontus von Brömssen)

Cf. A000245, A151890, A349594 (2nd row/column), A349596 (3rd row/column) A365629 (4th row/column), A373037 (main diagonal).

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

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

Original entry on oeis.org

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

cp's OEIS Frontend

A373036 Triangle read by rows: T(n,k) is the number of edge subsets E of the n X k grid graph such that E contains a path between the top left node and the bottom right node, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

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