How many ways are there to pile $n$ "$1\times 2$ rectangles" under some conditions?

Question

A friend of mine taught me the following question. He said he created the question by himself and conjectured the answer, but couldn't prove it. Though I've tried to solve the question, I've been facing difficulty.

The question is about piling rectangles. (The following is an example when we pile thirteen $1\times 2$ rectangles.)

$\qquad\qquad\qquad\qquad$

Question : For a positive integer $n$, how many ways are there to pile $n$ $1\times 2$ rectangles ("$1$ row and $2$ columns" only) under the following conditions?

• The rectangles at the bottom are next to each other.

• A rectangle not at the bottom and another rectangle right below it "overlap" only half.

Let $f(n)$ be the number of such ways. Then, interestingly, we have $$f(1)=1,\quad f(2)=3,\quad f(3)=9,\quad f(4)=27,\quad f(5)=81,\cdots$$

We have $f(3)=9$ because

$\qquad\qquad$

So, it seems that we can have $f(n)=3^{n-1}$. However, I have not been able to prove that.

I've tried to use induction. However, I have not been able to find a way to use the induction hypothesis. Since the answer seems very simple, there should be something that I'm missing. Can anyone help?

Answer 1

This result is contained in Corollary 5.3 in [1]:

The number of directed animals on the square lattice of size $n$ with [...] compact sources, is $3^{n-1}.$

Exercise for the reader: Show that the rectangle piling problem on $n$ tiles proposed here is equivalent to counting directed animals of size $n$ on the 2-dimensional square lattice with compact sources.

Definition: A directed animal $A$ (on the 2-d square lattice $\mathcal{L}$) is a subset of points of $\mathcal{L}$ such that:

• There is a distinguished non-empty set $S \subseteq A \subseteq \mathcal{L}$ called "sources"
• For every point $p$ in $A$ there is a path $P$ from some source $s \in S$ such that the points in $P$ are contained in $A$ and $P$ consists solely of north and east unit moves along the lattice

Definition: A directed animal has compact sources iff the set of sources may be specified as the points $(-s,s), s=1,2,\ldots,k$ for some $k$.

1) Barcucci, Elena, et al. "Directed animals, forests and permutations." Discrete mathematics 204.1 (1999): 41-71.

Answer 2

This problem is very similar to a problem of fixed hexagonal polyominoes. Each rectangle has six points of contact with its surrounding rectangles, and those contacts are independent of each other. We may equally replace the rectangles with hexagons. This is a difficult open problem; a fairly recent paper by Voge and Guttmann in J. Theoretical Computer Science computed a table up to n=35 (on p.444), as well as a variety of bounds and asymptotic results.

What makes this problem different from the above is a gravity condition. It allows this position:

o o X
X X

but does not allow this position:

o X X
X o

Consequently, all I can conclude from the above reference is that Voge/Guttman's values are upper bounds for the desired numbers. The gravity condition may make the problem harder or easier, it is hard to tell at first glance. My guess is harder, and my followup guess is that the powers-of-three pattern identified is a coincidence.

Answer 3

Odlyzko and Wilf talk about "fountains of coins", where you have a contiguous row of coins on the bottom, and over that coins which touch exactly two coins of the lower row. This is similar to the "halfway" restriction here, but differs in that e.g. the second example is forbidden (as is the example with 13 blocks). If all rows are contiguous, and the bottom row has $n$ coins, the number of block fountains is essentially an odd Fibonacci number.

Answer 4

(Too long for a comment) Here is the histogram of the base lengths for each count of tiles, suggested by Noam Elkies. $$\begin{array}{c|cccccccccccc} Tiles&Base\\ 1&1& \\ 2&2& 1& \\ 3&5& 3& 1\\ 4&13& 9& 4& 1\\ 5&35& 26& 14& 5& 1\\ 6&96& 75& 45& 20& 6& 1\\ 7&267& 216& 140& 71& 27& 7& 1\\ 8&750& 623& 427& 238& 105& 35& 8& 1\\ 9&2123& 1800& 1288& 770& 378& 148& 44& 9& 1 \end{array}$$ I can see, if $F(t,b)$ is the number of patterns with $t$ tiles and baselength $b$, then $F(t+1,1)=2F(t,1)+F(t,2)$. If there is only one tile on the bottom row, then the second row has at most two. But other recursions are bigger. for example $F(t+1,2)=3F(t-1,1)+2F(t-1,2)+F(t-1,3)+F(t,3)$.
Another option is to count the number of patterns of given height.
$$\begin{array}{c|ccccccccc}Tiles&Height\\ 1&1 \\ 2&1& 2 \\ 3&1& 4 & 4\\ 4&1& 7& 11& 8\\ 5&1& 12& 24& 28& 16\\ 6&1& 20& 52& 70& 68& 32\\ 7&1& 33& 110& 168& 193& 160& 64\\ 8&1& 54& 228& 401& 497& 510& 368& 128\\ 9&1& 88& 467& 944& 1257& 1412& 1304& 832& 256\\ \end{array}$$ There are some patterns here; for example, the number of height two is one less than a Fibonacci number.