The Number of Ribbon Tilings for Strips

2023/07/03 by Chen, Yinsong, Kargin, Vladislav
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2307.00767

Abstract

First, we consider order-n ribbon tilings of an M-by-N rectangle R_M,N where M and N are much larger than n. We prove the existence of the growth rate γ_n of the number of tilings and show that γ_n ≤ (n-1) ln 2. Then, we study a rectangle R_M,N with fixed width M=n, called a strip. We derive lower and upper bounds on the growth rate μ_n for strips as ln n - 1 + o(1) ≤ μ_n ≤ ln n . Besides, we construct a recursive system which enables us to enumerate the order-n ribbon tilings of a strip for all n ≤ 8 and calculate the corresponding generating functions.

Related

• An upper bound on the per-tile entropy of ribbon tilings
• Generating functions for straight polyomino tilings of narrow rectangles
• Ribbon Tilings and Multidimensional Height Functions
• Tiling of Strip Lattices and Asymptotics
• A rigidity property of ribbon L-shaped n-ominoes and generalizations