Suppose I am given a set of $n$ intervals, each having length $\ell\_i$. Is there a bound on the number of possible orderings of their left and right endpoints? For example, if each interval is represented by $[x\_i,y\_i]$, with $y\_i-x\_i=\ell\_i$, then one possible ordering would be $x\_1\leq x\_3\leq y\_1\leq x\_2 \leq y\_2 \leq y\_3$. If the lengths are not fixed, then it is clear that the number of orderings is $(2n)!/2^n$. Does fixing the lengths permit a significantly better upper bound?



Enumerating all arrangements of intervals with given lengths
If all the interval lengths are the same, then the number of ways is
$n!C\_n$, where $C\_n$ is a Catalan number. If we are interested only in
the number of ways we can specify whether $y\_i<x\_j$ or $x\_j<y\_i$ for
all $i,j$, then the number of ways is the number of regions of the
hyperplane arrangement $\mathcal{A}(\ell\_1,\dots,\ell\_n)$ in
$\mathbb{R}^n$ with hyperplanes
$x\_i-x\_j=\ell\_i$, for $1\leq i<j\leq n$. If the $\ell\_i$'s are
sufficiently generic (e.g., linearly independent over $\mathbb{Q}$ or
super-increasing) and if $c\_n$ is the number of regions of
$\mathcal{A}(\ell\_1,\dots,\ell\_n)$, then the generating function
$z=\sum\_{n\geq 0}c\_n\frac{x^n}{n!}$ is uniquely determined by the
condition $\frac{z'}{z}=y^2$, $z(0)=1$, where $1=y(2-e^{xy})$.
See <http://math.mit.edu/~rstan/papers/nas.pdf>.


**Addendum.** For the actual question, the number $f(n)$ of
arrangements is the number of regions of the hyperplane arrangement
$\mathcal{I}\_n$ defined by
 $$ x\_i - x\_j = 0,\ \ i<j $$
 $$ x\_i - x\_j = \ell\_i,\ \ i\neq j $$
 $$ x\_i-x\_j = \ell\_i-\ell\_j,\ \ i\neq j. $$
An upper bound would be the number $g(n)$ of regions of
 $$ x\_i-x\_j = a\_{ij}, b\_{ij}, c\_{ij}, d\_{ij}, e\_{ij}, $$
where the $a\_{ij}$'s, $\dots, e\_{ij}$'s are generic. This
number is given by
 $$ g(n) = \sum\_F 5^{e(F)}, $$
where the sum is over all forests $F$ on $n$ vertices, and $e(F)$ is
the number of edges of $F$. It has the generating function
 $$ \sum\_{n\geq 0}g(n)\frac{x^n}{n!} = \exp \sum\_{i\geq 1} 5^{i-1}
 i^{i-2}\frac{x^i}{i!}. $$
I wonder how close this upper bound is to $f(n)$.


With a little more work, one should be able to give a slightly better
upper bound by computing the number of regions of
 $$ x\_i-x\_j = 0, a\_{ij}, b\_{ij}, c\_{ij}, d\_{ij}. $$
It may even be possible to compute the number of regions of
$\mathcal{I}\_n$ itself when the $\ell\_i$'s are generic using methods 
similar to those used for
$\mathcal{A}(\ell\_1,\dots,\ell\_n)$. Details of the proof are in 
Section 6 of <http://math.mit.edu/~rstan/papers/deform.pdf>.


The interpretation of $f(n)$ in terms of hyperplane arrangements has
the interesting consequence that as long as the $\ell\_i$'s are
sufficiently generic real numbers (in particular, the set of
nongeneric $(\ell\_1,\dots,\ell\_n)\in\mathbb{R}^n$ has measure 0), the
number $f(n)$ of arrangements depends only on $n$. Note that the set
of possible orderings of the $x\_i$'s and $y\_i$'s *does* depend on the
actual generic $\ell\_i$'s.


