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.

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

Offset: 1

Author

Eugene Nonko, Nov 22 2021

Keywords

• nonn
• easy

Comments

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

Links

• 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).

Crossrefs

Cf. A349594.

Third row/column of A373036.

Formula

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

Extensions

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

Name clarified by Eugene Nonko, Nov 18 2024