### Overview


For integers n ≥ 1, let T(n) = {0,1,...,n}n and B(n)= {0,1}n. Note that |T(n)|=(n+1)n and |B(n)| = 2n.
A certain set S(n) ⊂ T(n), defined below, contains B(n). The question is about the growth rate of |S(n)|. Does it grow exponentially, like |B(n)|, so that |S(n)| ~ cn for some c, or does it grow superexponentially, so that cn/|S(n)| approaches 0 for all c> 0?


### Definition


The set S(n) is defined as follows: an n-tuple t = (t1,t2,...,tn) ∈ T(n) is in S(n) if and only if ti+j ≤ j whenever 1 ≤ j< t i. For example, if t ∈ T(10) with t 4=5, t 5 can be at most 1, t 6 can be at most 2, , t 7 can be at most 3, and t 8 at most 4, but there is no restriction (at least not due to the value of t 4) on t 9 or t 10; t 9 and t 10 can have any values in {1,...,10}.


### Alternate formulation (counting triangles)


The elements of S(n) can be put into one-to-one correspondence with certain configurations of n right isosceles triangles, so that |S(n)| counts the number of such configurations. 


For integers k>0 (size) and v≥0 (vertical position), let Δ k,v be the triangle with vertices (0,v), (k,k+v), and (k,v). (Δ0,v is the degenerate triangle with all three vertices at (0,v).)


Now associate with an n-tuple t = (t1,t2,...,tn) ∈ T(n) the set Dt = $\lbrace\Delta\_{t\_k,k}:1\le k \le n\rbrace$. (That's "\lbrace\Delta\_{t\_k,k}:1\le k \le n\rbrace," if you can't read it.) The set D t contains n isosceles right triangles that extend to the right of the y-axis, one triangle at each of the points (0,k) for 1 ≤ k ≤ n.


The tuple t is in S(n) if and only if the triangles in D t have disjoint interiors. (This isn't hard to show, and if it is, I've probably made a mistake in my definitions, so let me know.) Thus |S(n)| counts the number of ways one can arrange n isosceles right triangles of various sizes (between size zero and size n) at n consecutive integer points on the y-axis so the triangle can extend to the right and up without overlapping. Triangles of the same size are indistiguishable for the purpose of counting the number of arrangements. (It may help to think of right isosceles pennants attached at an acute-angle corner to a flagpole in a stiff wind.)


### Question


Does |S(n)| grow exponentially with n, or faster?


### Calculations


If I’ve counted correctly, the first few terms of the sequence {|S(n)|} beginning with n=1 are 2, 8, 38, 184, 904, and 4384. This sequence (and some sequences resulting from minor variations of the problem) fails to match anything in the Online Encyclopedia of Integer Sequence.


Links to similar counting problems mentioned or solved in the literature would help. 


Thanks!



Counting certain arrangements of n triangles. Does the count grow superexponentially?
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,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.


