login
A334875
Number of tribone tilings of an n-triangle.
1
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,10
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.
PROG
(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)]
CROSSREFS
The sequence of nonzero indices is A072065.
Cf. A155219.
Sequence in context: A271034 A185965 A106193 * A328476 A085814 A009524
KEYWORD
nonn,hard
AUTHOR
Jonathan Oswald, May 13 2020
EXTENSIONS
Name clarified by James Propp, Mar 28 2022
STATUS
approved