Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Metadata 
bibkey: kagey2018a301976
authors: Peter Kagey; Colin Barker
year: 2018
title: "OEIS A301976, Number of no-leaf subgraphs of the 3 X n grid"
doi: null
url: https://oeis.org/A301976
claim: "A301976 %N: Number of no-leaf subgraphs of the 3 X n grid. A301976 %C: Also, the number of ways to lay unit-length matchsticks on a 3 X n grid of points in such a way that no end is \"orphaned\". A301976 %C: Conjecture: a(n) mod 10 = 3 for n > 2. A301976 %F: Conjectures from _Colin Barker_, Mar 30 2018: (Start) G.f.: x*(1 + x)*(1 - 8*x - 3*x^2) / (1 - 12*x + 6*x^2 + 20*x^3 + 5*x^4). a(n) = 12*a(n-1) - 6*a(n-2) - 20*a(n-3) - 5*a(n-4) for n>4. (End) A301976 %A: _Peter Kagey_, Mar 29 2018"
strata_touched:
  - D5/S1/Words/Patterns/GridNoLeafSubgraphRecurrence
license: citation-only
triage: anchor

OEIS A301976

The entry counts spanning edge-subgraphs of the 3 X n grid graph in which every vertex has degree different from one; isolated vertices are allowed. It gives the initial values 1, 5, 43, 463 and records Colin Barker’s generating function and order-four recurrence together with Peter Kagey’s modulo-ten conjecture.

The formal module represents each vertical or horizontal grid edge by one of five labels in its left or lower column. It proves Barker’s recurrence for every n > 4 and Kagey’s congruence for every n > 2. The generating-function line is not separately formalized.

Verified locator

  • URL: https://oeis.org/A301976
  • Locator: COMMENTS, “Conjecture: a(n) mod 10 = 3 for n > 2.”
  • Locator: FORMULA, “a(n) = 12a(n-1) - 6a(n-2) - 20a(n-3) - 5a(n-4) for n>4.”