26
$\begingroup$

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$enter image description here

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$enter image description here

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?

$\endgroup$
7
  • $\begingroup$ A related question, where each rectangle must touch two rectangles in the row below, is an example in Richard Guy's "The Strong Law of Small Numbers" of an apparent pattern that fails to hold up. $\endgroup$
    – Julian Rosen
    Oct 12, 2015 at 16:48
  • $\begingroup$ I think that you're seeing a sum of independent things that will later fail to be independent for larger $n$ and kill this pattern. For instance, if you have a base 2 tiles in width, and two towers built on top of it, one on the leftmost position and one on the rightmost, they are independent until $n = 7$. I will think about this more. $\endgroup$
    – Eric Tressler
    Oct 12, 2015 at 16:55
  • $\begingroup$ @JulianRosen: Thank you for the information. It sounds interesting. $\endgroup$
    – mathlove
    Oct 12, 2015 at 17:00
  • $\begingroup$ @EricTressler: Thank you for sharing your thought. I'll think about it too. $\endgroup$
    – mathlove
    Oct 12, 2015 at 17:03
  • 3
    $\begingroup$ If my program is correct, it holds true through to $f(11)=59049$ $\endgroup$
    – Empy2
    Oct 15, 2015 at 7:16

4 Answers 4

Reset to default
9
+50
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Interesting reference! +1 $\endgroup$
    – Markus Scheuer
    Oct 20, 2015 at 13:58
  • $\begingroup$ I'm very glad to know the reference. Thank you so much! $\endgroup$
    – mathlove
    Oct 21, 2015 at 10:16
6
$\begingroup$

(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.

$\endgroup$
4
  • $\begingroup$ More than a comment! +1 $\endgroup$
    – Markus Scheuer
    Oct 19, 2015 at 16:22
  • $\begingroup$ The first sequence is A038622; the second is not in the OEIS. $\endgroup$
    – RavenclawPrefect
    Oct 20, 2015 at 19:00
  • 4
    $\begingroup$ I found the connection to "directed animals" by checking OEIS for each of the columns in the first table. $\endgroup$
    – mhum
    Oct 20, 2015 at 23:40
  • $\begingroup$ Thank you for your help! +1 $\endgroup$
    – mathlove
    Oct 22, 2015 at 9:55
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Where is there a gravity condition? I don't see one stated in the OP. $\endgroup$
    – Brian Tung
    Oct 12, 2015 at 17:15
  • $\begingroup$ Gravity is implicit in the problem; each rectangle must rest on something. Take the second or fourth examples and reflect them in a horizontal line to get the forbidden positions. Including these would bring the total to 11, which matches the Voge/Guttman table. $\endgroup$
    – vadim123
    Oct 12, 2015 at 17:22
  • $\begingroup$ Ahh, well, I took gravity to mean actual stability. For instance, the very last example in OP is not stable: It should tip to the right and fall down. If you mean by gravity only that each rectangle must overlap a rectangle below it by $1/2$, then yes, I see that. $\endgroup$
    – Brian Tung
    Oct 12, 2015 at 17:24
  • $\begingroup$ A stability condition would be considerably stronger than the gravity condition here; only two of the nine given arrangements are stable. $\endgroup$
    – vadim123
    Oct 12, 2015 at 17:26
  • $\begingroup$ I know (well, I treat exact $1/2$ overlaps as quasi-stable), but I consider "gravity" as used ordinarily to include "stability." Anyway, now I know what you mean. $\endgroup$
    – Brian Tung
    Oct 12, 2015 at 17:30
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .