16
$\begingroup$

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!

$\endgroup$
6
  • 1
    $\begingroup$ That's a very nice question! $\endgroup$ Aug 6, 2010 at 8:15
  • $\begingroup$ The answer is probably yes: ($|S(n)|$ has only exponential growth. Indeed, the computation of $|S(n)|$ for $n\leq 100$ shows experimentally that the consecutive ratios $q(i)=|S(i+1)|/|S(i)|$ are decreasing (the computed value is $q(99)\sim 4.4844$) for $4\leq i\leq 99$. (By the way, your first values seem correct. I got $259024814181457754778436963733785051716113923919290629264571891712$ for the last value $|S(100)|$.) $\endgroup$ Aug 6, 2010 at 17:09
  • $\begingroup$ Thanks, Roland! I'm impressed with how far you calculated this. Could you give me a hint as to how you did it? $\endgroup$
    – Steve Kass
    Aug 6, 2010 at 20:42
  • $\begingroup$ Nitpicking: In the example following the first definition, you state that setting t_4=5 restricts t_9 to be at most 5, but it does not. $\endgroup$ Aug 7, 2010 at 21:13
  • $\begingroup$ @Tsuyoshi: Thanks! I've edited my question to correct the error. $\endgroup$
    – Steve Kass
    Aug 8, 2010 at 0:04

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

This is no answer but a description of an efficient way for computing the cardinality of $S(n)$. I have to post it as an answer since it is too long for a comment.

Consider the subsets $U_a(n),C_a(n),L_a(n)$ of $S(n)$ defined as follows: all coefficients of $U_a(n),C_a(n),L_a(n)$ are $\leq a$ and satisfy the additional inequalities $t_i\leq i$ for $U,C$, respectively $t_{n-i}\leq i+1$ for $C,L$.

The set $S(n)$ is then in bijection with the union of the trivial element $(0,0,\dots,0)$ with $\cup_{\mu=1}^n\cup_{k=1}^n L_\mu(k-1)\times U_{\mu-1}(n-k)$. Indeed, a non-trivial element $(t_1,\dots,t_n)\in S(n)$ with last index $k$ on which its coefficient takes the maximal value $\mu=\max_i t_i$ gives rise to an element $(t_1,\dots,t_{k-1})$ of $L_\mu(k-1)$ and to an element $(t_{k+1},t_{k+2},\dots,t_n)$ of $U_{\mu-1}(n-k)$. These elements, together with the omitted $k-$th coordinate $t_k=\mu$, determine the initial vector $(t_1,\dots,t_n)$ uniquely.

One gets similar recursive decompositions of $U,C,L$ (standing for upper, central, lower) giving rise to recurrence relations among the cardinalities of $U,C,L$ which allow to compute their cardinalities in quadratic time.

By the way, here an idea which can perhaps be exploited: Elements of $S(n)$ with no coordinate equal to $0$ are in bijection with a subset (which can explicitely be described) of $\cup_{k=\lfloor n/2\rfloor}^{n-1}S(k)$ as follows: replace every coefficient $t_i$ of such an element $(t_1,\dots,t_n)$ by $t_i-1$ except if $t_i=1$ and $t_{i-1}>1$ in which case you remove it.

$\endgroup$
3
$\begingroup$

Edit: I worked out the details of this exponential upper bound a bit more precisely. It is the case that $S(n) \leq 11*10^n$.

I can only prove an exponential upper bound (rather than an exponential asymptotic), but it can be obtained by weakening your restriction on the vectors $S(n)$ as follows: the value of $t_m$ restricts $t_{m+i}$ to be less than $t_m$ for $i < t_m$. (This replaces your "triangular" barriers with "backwards-L-shaped" barriers.) I'll call this new set of vectors $U(n)$. In fact, it's then useful to generalize slightly -- I'll write $U(n,m)$ for the set of vectors $(u_1,\ldots,u_n) \in \lbrace 0,1,\ldots,m\rbrace^{n}$ that have the above kind of restriction. (So in this notation we have $S(n) \subset U(n) = U(n,n)$). For any $n$ and $m$, by considering the value of the first element of the vector, we have the recursion $$ U(n+1,m) = 2U(n,m) + \sum_{k=2}^{\min(n,m)} ( U(k-1,k-1) + U(n+1-k,m) ) + \sum_{k=\min(n,m)+1}^m U(n,k). $$ The first term on the RHS corresponds to when $u_1=0$ or $u_1=1$, and the second corresponds to when $u_1 > n$.

From this recursion you can get exponential upper bounds by induction. For the base cases, note that $U(1,m)=m+1$ for all $m$, and $U(n,1)=2^n$ for all $n$ (though I don't think the latter is necessary for the following argument). If we then try to get bounds of the form $U(n,m) \leq (m+1)a^mb^n$, then the base case holds as long as $a \geq 1$ and $b \geq 2$. However, the induction is easy if you take $a=2$ and $b=5$; then just by plugging in the inductive bounds and doing a few geometric sums, you derive the same bound for $U(n,m)$.

In particular, the above argument shows that $U(n,n) \leq 11*10^n$, which is likely far from tight. Of course, you can probably figure out precise asymptotics for $U$ from the above recurrence with a little more work, but given that it won't yield asymptotics for $T$ maybe just the upper bound is enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.