show/hide this revision's text 3 edited body

Your sequence is bounded by $(125+\epsilon)^n$. Obviously, this isn't close to a good bound, but it answers the question.

We start by bounding a different question: Let $\Gamma_n$ be the convex hull of $(0,0)$, $(0,n)$ and $(n,0)$. (n,n)$. (So $\Gamma$ is rotated $180^{\circ}$ with respect to your $\Delta$.) Let $q_n$ be the number of ways to pack non-overlapping triangles into $\Gamma_n$.

Given any packing of triangles in $\Gamma_n$, which uses at least one triangle, let the largest triangle be of size $k$ and have a vertex at $(0,r)$. (If there is more than one largest triangle, make an arbitrary choice; this will just lead to a larger bound in the end.) So all the other triangles must fit into one of two trapezoids: one with base $r$ and height $k$ and the other with base $n-r$ and height $k$. In any case, these two trapezoids fit into translations of $\Gamma_r$ and $\Gamma_{n-r}$. So we obtain the inequality $$q_n \leq \sum_{r=1}^{n-1} q_r q_{n-r} + 1,$$ where the $+1$ is because we have to remember the possibility that there might be no triangles in the packing. If we take $q_0=0$ for convenience, we get that $\sum q_n z^n$ is term by term dominated by the solution of $$Q(z) = Q(z)^2 + \frac{z}{1-z}.$$ Solving the quadratic, $$Q(z) = \frac{1}{2} \left( 1 - \sqrt{1-\frac{4z}{1-z}} \right).$$ Notice that $Q(z)$ has radius of convergence $1/5$ so $q_n \leq (5+\epsilon)^n$.

I previously had an argument here that didn't work, so here is something even more sloppy. All the triangles you are considering fit inside $\Gamma_{3n}$. So your quantity is bounded by $q_{3n}$, and hence by $(125+\epsilon)^n$.

I suspect that $5^n$ may be pretty close to the right rate of growth, especially given Roland Bacher's computation.
show/hide this revision's text 2 deleted 620 characters in body; added 1 characters in body

Your sequence is bounded by $(25+\epsilon)^n$. (125+\epsilon)^n$. Obviously, this isn't close to a good bound, but it answers the question.

It will also be convenient to have a notation for the generating function$$R(z) := \sum q_{2n} z^n = \frac{1}{2} \left( Q(\sqrt{z}) + Q(- \sqrt{z}) \right).$$Notice that $Q(z)$ has radius of convergence $1/5$, and $R$ has radius of convergence 1/5$ so $1/25$.

Look at a packing of triangles into your shape. Once againq_n \leq (5+\epsilon)^n$.

I previously had an argument here that didn't work, let the largest triangle have size $k$ and a vertex at $(0,r)$. So all so here is something even more sloppy. All the other triangles fit into two parallelograms of height $k$: one with base $r$ and one with base $n-r$. These, in turn, you are considering fit into triangles $\Gamma_{2r}$ and inside $\Gamma_{2n-2r}$. \Gamma_{3n}$. So your quantity is bounded by $$\sum_{r=0}^{n} q_{2r} q_{2n-2r}.$$In other words, your generating function is bounded term by term by $R(z)^2$. Since $R(z)^2$ has radius of convergence $1/25$, your function converges here as well, q_{3n}$, and your terms grow no faster than $(25+\epsilon)^n$.

I expect that a bit more care will get you to $(5+\epsilon)^n$: replacing those parallelograms hence by triangles is incredibly sloppy. $(125+\epsilon)^n$.

I suspect that pushing past $5$ will require some effort5^n$ may be pretty close to the right rate of growth, especially given Roland Bacher's computation.
show/hide this revision's text 1

Your sequence is bounded by $(25+\epsilon)^n$. Obviously, this isn't close to a good bound, but it answers the question.

We start by bounding a different question: Let $\Gamma_n$ be the convex hull of $(0,0)$, $(0,n)$ and $(n,0)$. (So $\Gamma$ is rotated $180^{\circ}$ with respect to your $\Delta$.) Let $q_n$ be the number of ways to pack non-overlapping triangles into $\Gamma_n$.

Given any packing of triangles in $\Gamma_n$, which uses at least one triangle, let the largest triangle be of size $k$ and have a vertex at $(0,r)$. (If there is more than one largest triangle, make an arbitrary choice; this will just lead to a larger bound in the end.) So all the other triangles must fit into one of two trapezoids: one with base $r$ and height $k$ and the other with base $n-r$ and height $k$. In any case, these two trapezoids fit into translations of $\Gamma_r$ and $\Gamma_{n-r}$. So we obtain the inequality $$q_n \leq \sum_{r=1}^{n-1} q_r q_{n-r} + 1,$$ where the $+1$ is because we have to remember the possibility that there might be no triangles in the packing. If we take $q_0=0$ for convenience, we get that $\sum q_n z^n$ is term by term dominated by the solution of $$Q(z) = Q(z)^2 + \frac{z}{1-z}.$$ Solving the quadratic, $$Q(z) = \frac{1}{2} \left( 1 - \sqrt{1-\frac{4z}{1-z}} \right).$$ It will also be convenient to have a notation for the generating function $$R(z) := \sum q_{2n} z^n = \frac{1}{2} \left( Q(\sqrt{z}) + Q(- \sqrt{z}) \right).$$ Notice that $Q(z)$ has radius of convergence $1/5$, and $R$ has radius of convergence $1/25$.

Look at a packing of triangles into your shape. Once again, let the largest triangle have size $k$ and a vertex at $(0,r)$. So all the other triangles fit into two parallelograms of height $k$: one with base $r$ and one with base $n-r$. These, in turn, fit into triangles $\Gamma_{2r}$ and $\Gamma_{2n-2r}$. So your quantity is bounded by $$\sum_{r=0}^{n} q_{2r} q_{2n-2r}.$$ In other words, your generating function is bounded term by term by $R(z)^2$. Since $R(z)^2$ has radius of convergence $1/25$, your function converges here as well, and your terms grow no faster than $(25+\epsilon)^n$.

I expect that a bit more care will get you to $(5+\epsilon)^n$: replacing those parallelograms by triangles is incredibly sloppy. I suspect that pushing past $5$ will require some effort.