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

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

2010-08-06T03:01:58Z

Overview

For integers n ≥ 1, let T(n) = {0,1,...,n}ⁿ and B(n)= {0,1}ⁿ. Note that |T(n)|=(n+1)ⁿ and |B(n)| = 2ⁿ. 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ⁿ for some c, or does it grow superexponentially, so that cⁿ/|S(n)| approaches 0 for all c> 0?

Definition

The set S(n) is defined as follows: an n-tuple t = (t₁,t₂,...,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₄=5, t₅ can be at most 1, t₆ can be at most 2, , t₇ can be at most 3, and t₈ at most 4, but there is no restriction (at least not due to the value of t₄) on t₉ or t₁₀; t₉ and t₁₀ 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₁,t₂,...,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!

Answer by Roland Bacher for Counting certain arrangements of n triangles. Does the count grow superexponentially?

2010-08-07T09:01:47Z

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.

Answer by Louigi Addario-Berry for Counting certain arrangements of n triangles. Does the count grow superexponentially?

2010-09-13T20:29:21Z

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.

Answer by David Speyer for Counting certain arrangements of n triangles. Does the count grow superexponentially?

2010-09-14T01:44:20Z

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.