### 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)| = 2^{n}.
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)| ~ c^{n} for some c, or does it grow superexponentially, so that c^{n}/|S(n)| approaches 0 for all c> 0?

### Definition

The set S(n) is defined as follows: an n-tuple t = (t_{1},t_{2},...,t_{n}) ∈ T(n) is in S(n) if and only if t_{i+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 = (t_{1},t_{2},...,t_{n}) ∈ T(n) the set D_{t} = $\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!

1more comment