How many combinatorially distinct ways are there to tile an equilateral triangle with $k$ $60^\circ-120^\circ$ trapezoids?

I believe there is exactly one way (up to combinatorial equivalence) to arrange 3 trapezoids with angles of $60^\circ$ and $120^\circ$ into an equilateral triangle:

With $4$ trapezoids, I see two ways:

With $5$ trapezoids, there are many more; I count at least $13$ (thanks to Dan Uznanski for discovering the last of these):

In general, how many ways are there to do this with $k$ trapezoids, and what are the corresponding arrangements?

Knowing that the sequence starts $1,2,13?,\ldots$ isn't quite enough to try and find it on OEIS. (I'd also appreciate hearing about any configurations that I may have missed above.)

Edit: It seems that the terminology above was not clear to everyone, so two clarifications:

• When I say "trapezoids" here, I am referring only to those pictured above, where there is exactly one pair of parallel sides and the $60^\circ$ angles are adjacent; I am not including parallelograms with angles in cyclic order $(60^\circ, 120^\circ, 60^\circ, 120^\circ)$.

• Two arrangements are combinatorially equivalent if there is a bijection between the corners, edges, and faces of the two which preserves inclusion (e.g. of a vertex on a face or one line segment in another), adjacency, overlaps, and maps $60^\circ$ and $120^\circ$ angles in trapezoids to themselves. In other words, we care about the incidence structure of the trapezoids, and whether trapezoids $A$ and $B$ coincide along a shared leg, but not about specific lengths of line segments or a rotation of the large triangle.

Solution 1:

Correction and revision added at the end

An equilateral triangle tiled with $k$ $60^o-120^o$ trapezoids can be tiled with $k+1$ such trapezoids in at least six ways: by adding a tile along the whole of one side of the equilateral triangle, or by dividing one of the tiles whose base does not occupy an entire side of the triangle. But when $k=3$, the first three arrangements for $k+1$ are equivalent under $120^o$ rotation, as are the second three, and so we have only two distinct tilings for $k=4$, as OP notes, which we may denote as $4a$ and $4b$.

We can add a tile to $4a$ in six distinct ways, as in the first six of OP's array for $k=5$ (reading left to right and down). Of the six ways to add a tile to $4b$, four are equivalent to one of the preceding six, and so we have only two distinct new tilings, the seventh and eighth in OP's illustration.

But we can also add a tile to $4b$ by re-dividing the divided trapezoid of $4b$ in one of the three ways shown in OP's ninth, eleventh, and twelfth figures of the array.

Lastly, reducing the number of concurrent lines from the sides of the triangle from three (as in all preceding cases) to two, i.e. by removing one of them, we can re-tile the remaining concave pentagon with four tiles in exactly two distinct ways, as in OP's tenth and thirteenth.

Thus from $4a$ and $4b$ we derive $5a$, $5b_1$ and $5b_2$, with distinct arrangements$$5a+5b_1+5b_2=6+2+5=13$$

If these thirteen distinct tilings for $k=5$ are complete, then for $k=6, 7, 8$ I find, by systematic counting, $68, 283, 1081$ distinct tilings, respectively.

Looking at these totals part by part, i.e. as generated by $5a+5b_1+5b_2$ and their descendants, we have

$$[1+1+1+1+1+1]+[1+1]+[1+1+1+1+1]=13$$for $k=5$,$$[1+2+3+6+6+6]+[3+1]+[8+8+8+8+8]=68$$for $k=6$,$$[1+3+6+24+24+24]+[6+0]+[39+39+39+39+39]=283$$for $k=7$, and$$[1+4+10+82+82+82]+[10+0]+[152+152+152+152+152]=1031$$for $k=8$.

I. In the bracketed $6$-sums on the left, the pattern of the first three (vertical) columns is clear: $1$'s in the first column, consecutive integers in the second, and consecutive triangle numbers in the third, starting from $1$. The greatest addend in each (horizontal) row is equal to the sum of the six addends in the row preceding. As a function of $k$, the sum of the first three terms in each row is thus given by$$\frac{k^2-5k+6}{2}$$The sequence of identical greatest terms in each row, easily extendable to $$1, 6, 24, 82, 261, 804, 2440, 7356, 22115,...$$ is given by the expression$$\Sigma\Sigma\frac{3^{k-4}-1}{2}$$where $k\ge5$. This is clear since $$\Sigma\frac{3^{k-4}-1}{2}=1, 4, 13, 40, 121, 364,...$$and $$\Sigma\Sigma\frac{3^{k-4}-1}{2}=1(k-4)+4(k-5)+13(k-6)+40(k-7)+121(k-8)+...$$Thus by addition, the sum of the first bracketed row of six terms is$$\frac{k^2-5k+6}{2}+3[1(k-4)+4(k-5)+13(k-6)+40(k-7)+121(k-8)+...]$$II. For $k>6$, the second term derived from $4b_1$ yields no new tilings, and the bracketed middle addend is simply the triangle number given by$$\frac{k^2-7k+12}{2}$$III. Lastly, the sequence of each column of the $5$-sums on the right,$$1,8,39,152,526,1704,5322,16296,...$$is OEIS A097787:$$\frac{3^{n+5}}{32}-\frac{2n^4+32n^3+196n^2+556n+633}{96}$$And since $n=k-5$, this can be written as$$\frac{3^k}{32}-\frac{2k^4-8k^3+16k^2-4k+3}{96}$$

And so we seem to have a method for a $3$-step calculation of the number of distinct tilings of an equilateral triangle by $k$ $60^o-120^o$ trapezoids. It would be good to fuse the above expressions into a single expression in $k$, but I have not yet been able to do it. The sequence of total distinct tilings $$1,2,13,68,283,1031,3449,10981,33994,103629,313354,943623,2835853,8514355,...$$does not appear in OEIS.

Correction/Revision

I. As OP’s comment points out, the above answer rests on a false premise, that every distinct $k+1$ tiling of the equilateral triangle arises either from the addition of one trapezoid along an entire side of a k-tiled triangle, or from the division of one of the trapezoidal tiles within the triangle by a line parallel to the trapezoid's base, as in the generation below of six $k=6$ tilings from the first of OP's thirteen $k=5$ tilings by adding a trapezoid along bottom, right, and left in the first row, and by bisecting in turn the three inner trapezoids in the second row. I followed this same order in producing and numbering all the arrangements initially found.

But although this method finds (when duplicates are set aside) a portion of the distinct $k+1$ tilings of the triangle, it does not find all of them. As the comment notes, the following tiling for $k=6$, for example, does not arise in this way from any of the distinct tilings for $k=5$. Indeed, even from OP's last five tilings for $k=5$, it appears there are at least two other ways to generate a $(k+1)$-tiling: transformation and trisection.

II. OP's #$2$ for $k=5$ arises by addition of one tile to $4a$, as in my method, but #$10$ does not arise from $k=4$ but rather by a transformation of #$2$ for $k=5$, in which trapezoid $a$ expands into $b$ and $b$ in turn expands into $c$. Similarly, OP's #$13$ rotated is a modification of #$11$, by expansion of $a$ into $b$ and $b$ into $c$.

The figure above missing from my count for $k=6$ arises by a like transformation of arrangement #$9$ of the sixty-eight I initially found. where again trapezoid $a$ has displaced some of $b$, and $b$ some of $c$, in the figure on the right compared with #$9$ on the left.

But such transformations commonly involve only two trapezoids, not three, and a single arrangement can yield more than one. Of distinct arrangements found by my method for $k=6$, seven of them yield one or two arrangements I missed. Figures on the left below are numbered by their place in the sixty-eight distinct arrangements I found for $k=6$ by addition/division from the (slightly re-ordered) thirteen figures for $k=5$, followed on the right by the primed figures my method missed.
Each of these transformations is a one-step process in which one trapezoid invades and incorporates part of an adjacent one, e.g. as in #$45$-#$45'$, or #$45$-#$45''$

Just as the last five of the (presumably) thirteen arrangements for $k=5$ were not discoverable by my method from the two arrangements for $k=4$, so for $k=6$ the ten (primed) arrangements above were missed by my method.

III. And the count is still not complete. OP's $9th$, $11th$, and $12th$ arrangements for $k=5$ arise by trisection of one of the trapezoids for $k=3$. Accordingly, if we trisect in turn each trapezoid of $4a$ and $4b$ in each of the three ways seen in OP's $9th$, $11th$, and $12th$ for $k=5$, the following six (of twenty-four possible) arrangements are new, and we now have $68+10+6=84$ distinct tilings for $k=6$.

IV. Similarly, exploring the possible arrangements for $k=7$, besides the $283$ found by addition/division applied to the arrangements for $k=6$, new arrangements appear both by the method of transformation as well as by the addition (by trisection) of two trapezoids to each distinct arrangement for $k=5$. Since each trapezoid in an arrangement for $k=5$ can be trisected in three different ways, this raises the possibility of$$5\cdot13\cdot3=195$$new arrangements, although this is reduced to $125$ when $70$ duplicates are set aside. Adding as well the nineteen new arrangements found to result from transformations gives$$283+19+125=427$$distinct arrangements for $k=7$.

It seems, then, there are three ways to generate a $k+1$ tiling: by adding one tile to a $k$-tiling, by adding (through trisection) two tiles to a $(k-1)$-tiling, and by transforming a $(k+1)$-tiling generated in one of the first two ways. Are there other ways? If not, are the above revised counts accurate? In searching for combinatorially distinct arrangements, I find the systematic survey of possible transformations more difficult than that of possible trisections. OEIS does not recognize sequence$$1, 2, 13, 84, 427$$ so it seems an expression in $k$ for the number of distinct tilings of the triangle must await an accurate count at least through $k=8$, if a general rule is to appear.