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