login
Number of no-leaf subgraphs of the 4 X n grid.
3

%I #21 Oct 20 2018 04:00:14

%S 1,15,463,16372,583199,20788249,741026781,26415034787,941604528692,

%T 33564941612743,1196473967526971,42650154782713601,

%U 1520330364358307239,54194514148101568538,1931846809485041315873,68863650758427752078777,2454750745501814744040599

%N Number of no-leaf subgraphs of the 4 X n grid.

%C Also, the number of ways to lay unit-length matchsticks on a 4 X n grid of points in such a way that no end is "orphaned".

%H Peter Kagey, <a href="/A320097/b320097.txt">Table of n, a(n) for n = 1..500</a>

%F Conjecture: a(n) = 36*a(n-1) - 7*a(n-2) - 201*a(n-3) + 49*a(n-4) + 20*a(n-5) - 5*a(n-6) for all n > 6.

%F Empirical g.f.: x*(1 - 21*x - 70*x^2 + 10*x^3 + 14*x^4 - 3*x^5) / (1 - 36*x + 7*x^2 + 201*x^3 - 49*x^4 - 20*x^5 + 5*x^6). - _Colin Barker_, Oct 20 2018

%e Three of the a(3) = 463 subgraphs of the 4 X 3 grid with no leaf vertices are

%e + +---+ + + + + +---+

%e | | | |

%e +---+---+ +---+---+ + +---+

%e | | , | | |, and .

%e +---+ + + +---+ +---+ +

%e | | | | | |

%e +---+ + +---+ + +---+ +

%Y A093129 is analogous for 2 X (n+1) grids.

%Y A301976 is analogous for 3 X n grids.

%K nonn

%O 1,2

%A _Peter Kagey_, Oct 05 2018