login
Number of no-leaf subgraphs of the 2 X n grid up to horizontal and vertical reflection.
1

%I #25 Oct 06 2018 14:30:13

%S 1,2,4,10,26,76,232,750,2493,8514,29524,103708,367225,1308542,4682276,

%T 16807286,60462082,217855460,785863048,2837177434,10249053629,

%U 37039804078,133902392980,484178868612,1751030978481,6333341963706,22909148647012,82872738727330

%N Number of no-leaf subgraphs of the 2 X n grid up to horizontal and vertical reflection.

%C The limit lim_{n -> infinity} A020876(n - 1)/a(n) = 4.

%H Peter Kagey, <a href="/A303930/b303930.txt">Table of n, a(n) for n = 1..1000</a>

%F Conjectures from _Colin Barker_, May 03 2018: (Start)

%F G.f.: x*(1 - 6*x + 4*x^2 + 30*x^3 - 45*x^4 - 22*x^5 + 60*x^6 - 20*x^7) / ((1 - 3*x + x^2)*(1 - 5*x + 5*x^2)*(1 - 5*x^2 + 5*x^4)).

%F a(n) = 8*a(n-1) - 16*a(n-2) - 20*a(n-3) + 95*a(n-4) - 60*a(n-5) - 80*a(n-6) + 100*a(n-7) - 25*a(n-8) for n>8.

%F (End)

%e For n = 4 the a(4) = 10 subgraphs of the 2 X 4 grid are:

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

%e | | | |

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

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

%e | | | | | | | | |

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

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

%e | | | | | | | | | |

%e +---+---+---+, +---+---+---+, +---+ +---+, and

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

%e | | |

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

%Y Cf. A020876, A301976.

%Y A093129 is analogous for 2 X (n+1) grids where reflections are considered distinct.

%K nonn

%O 1,2

%A _Peter Kagey_, May 02 2018