2 Corrected the error noted by Tsuyoshi Ito

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, and t 9 at most 5, 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 be have any value 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!

1

Counting certain arrangements of n triangles. Does the count grow superexponentially?

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, t 8 at most 4, and t 9 at most 5, but there is no restriction (at least not due to the value of t 4) on t 10; t 10 can be any value 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!