A334875 Number of tribone tilings of an n-triangle.

1, 0, 1, 0, 0, 0, 0, 0, 0, 2, 0, 8, 12, 0, 72, 0, 0, 0, 0, 0, 0, 185328, 0, 4736520, 21617456, 0, 912370744, 0, 0, 0, 0, 0, 0, 3688972842502560, 0, 717591590174000896, 9771553571471569856, 0, 3177501183165726091520, 0, 0, 0, 0, 0, 0

Offset: 0

Author

Jonathan Oswald, May 13 2020

Keywords

• nonn
• hard

Comments

This sequence was requested to be added by the author of the link Code Golf challenge. It is based on the work of J. H. Conway, who proved that n = 12k + 0,2,9,11 if and only if T(n) can be tiled (i.e., exactly covered without overlapping) by tribones.

Links

• Code Golf Challenge, Number of Distinct Tribone Tilings, posted by CGCC user Bubbler.
• J. H. Conway and J. C. Lagarias, Tiling with Polyominoes and Combinatorial Group Theory, Journal of Combinatorial Theory, Series A 53 (1990), 183-208.
• James Propp, Trimer covers in the triangular grid: twenty mostly open problems, arXiv:2206.06472 [math.CO], 2022.

Crossrefs

The sequence of nonzero indices is A072065.

Cf. A155219.

Programs

Python

# tribone tilings
def h(coords):
  def anyhex(i, j):
    c = [x in coords for x in [(i-1, j), (i, j+1), (i+1, j+1), (i+1, j), (i, j-1), (i-1, j-1)]]
    return any(map(lambda x, y: x and y, c, c[1:] + c[:1]))
  return all(anyhex(*z) for z in coords)
def g(coords):
  if not coords: return 1
  #if not h(coords): return 0
  i, j = min(coords)
  if (i+1, j+1) not in coords: return 0
  cases = 0
  if (i+1, j) in coords: cases += g(coords - {(i, j), (i+1, j), (i+1, j+1)})
  if (i, j+1) in coords: cases += g(coords - {(i, j), (i, j+1), (i+1, j+1)})
  return cases
def f(n):
  coords = {(i, j) for i in range(n) for j in range(i+1)}
  #if n%12 not in [0, 2, 9, 11]: return 0
  print(n, g(coords) if n%12 in [0, 2, 9, 11] else 0)
[f(x) for x in range(21)]

Extensions

Name clarified by James Propp, Mar 28 2022