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

1, 15, 463, 16372, 583199, 20788249, 741026781, 26415034787, 941604528692, 33564941612743, 1196473967526971, 42650154782713601, 1520330364358307239, 54194514148101568538, 1931846809485041315873, 68863650758427752078777, 2454750745501814744040599

Offset

1,2

Comments

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".

Links

Peter Kagey, Table of n, a(n) for n = 1..500

Formula

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.

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

Example

Three of the a(3) = 463 subgraphs of the 4 X 3 grid with no leaf vertices are
  +   +---+          +   +   +          +   +---+
      |   |                                 |   |
  +---+---+          +---+---+          +   +---+
  |   |    ,         |   |   |,   and            .
  +---+   +          +   +---+          +---+   +
  |   |              |   |              |   |
  +---+   +          +---+   +          +---+   +

Crossrefs

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

A301976 is analogous for 3 X n grids.

Sequence in context: A219561 A209488 A361307 * A177080 A306609 A272905

Adjacent sequences: A320094 A320095 A320096 * A320098 A320099 A320100

Keyword

nonn

Author

Peter Kagey, Oct 05 2018

Status

approved