Counting profile strings from rectangular tilings

Petrosino, Anthony; Schembor, Alissa; Haymaker, Kathryn

doi:10.2140/involve.2020.13.861

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Counting profile strings from rectangular tilings

Anthony Petrosino, Alissa Schembor and Kathryn Haymaker

Vol. 13 (2020), No. 5, 861–870

DOI: 10.2140/involve.2020.13.861

Abstract

We study the enumeration of profiles, which are outlines that occur when tiling a rectangular board with squares, dominoes, and trominoes. Profiles of length $m$ correspond to a special subset of the set ${0, 1, 2, 3}^{m}$ , called profile strings. Profiles and their corresponding strings first appeared in the enumeration of the tilings of rectangular $2 \times n$ and $3 \times n$ boards with squares, dominoes, and trominoes. Profiles also play a role in enumerating the tilings of an $m \times n$ board for any fixed $m \geq 2$ . We describe how profiles arise when enumerating tilings, and we prove that the number of profile strings of length $m$ equals $m \cdot 3^{m - 1}$ .

Keywords

rectangular tilings, enumeration, induction

Mathematical Subject Classification

Primary: 05A19, 05B45

Milestones

Received: 4 June 2020

Revised: 16 August 2020

Accepted: 17 August 2020

Published: 5 December 2020

Communicated by Arthur T. Benjamin

Authors

Anthony Petrosino
Villanova University Villanova, PA United States

Alissa Schembor
Villanova University Villanova, PA United States

Kathryn Haymaker
Villanova University Villanova, PA United States

Vol. 13, No. 5, 2020