Enumerating all arrangements of intervals with given lengths 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?
 A: Edit My criticism of Richard's post no longer applies after he edited it drastically, so I edited it out :-)
First, note that it is enough to bound the number of compatible pairs of permutations of $x$ and $y$ separately. Indeed, since we have at most ${2n\choose n}=e^{O(n)}$ insertions of those orders, we can that get the whole thing up to an exponential error, so if we are not after an exact asymptotics, we do not lose much this way.
To do it, we will just play with collision graphs. The idea is pretty simple: start moving intervals around without changing any of the two relevant orders until left ends or right ends of something nearly collide, after which move the tangled piece together until some more similar ends collide somewhere, and so on until we bring the configuration to a single piece. The graph is just the set of some disjoint red cliques corresponding to bunches of $x$-s that are all squashed nearly together and blue cliques corresponding to $y$'s. Note that the entire graph is connected (using both colors), so once we know the graph and the resolution of all cliques, we know the entire configuration. Suppose also that the lengths are generic (say, independent over $\mathbb Q$). If we are interested just in the strict orders, that can be done without any loss of generality. Our collision graph is then just a pair of disjoint clique graphs. Let us assume that the red graph has $k_j$ $j$-cliques and the blue graph $\ell_j$ $j$-cliques, so
$$
\sum_j jk_j=\sum_j j\ell_j=n\,.
$$
Now note that there are $\frac{n!}{(k_1!k_2!\dots)(1!)^{k_1}(2!)^{k_2}\dots}$ possible red graphs and, thereby, $\frac{n!}{k_1!k_2!\dots}$ resolved red graphs. Note also that such red graph has $\sum k_j$ components. Suppose that the red graph is given. Let us see where we can place the blue graph drawing its cliques in some natural order. Observe that when we do the first clique, we have to take all vertices from differentconnected components (otherwise we get a non-trivial relation between lengths) and once we draw it, we create a big stiff component that cannot have any more blue edges. Also, the number of components drops by the size of the clique minus one. The same argument (only the last sentence is relevant) applies to the second clique and so on. Thus, if the red and the blue graphs were compatible at all, we must have $n-\sum_j\ell_j\le \sum_j k_j$ (the component reduction should not exceed the number of components available from the beginning), i.e., $n\le\sum_j\ell_j+\sum_j k_j$ is a necessary compatibility condition.
Now we just forget anything except this last observation and write
$$
\frac{n!}{k_1!k_2!\dots}\frac{n!}{\ell_1!\ell_2!\dots}\le \frac{n!^2}{n^{n}}\frac {n^{k_1+k_2+\dots}}{k_1!k_2!\dots}\frac {n^{\ell_1+\ell_2+\dots}}{\ell_1!\ell_2!\dots}
$$
We need to sum such expressions over all $k$'s and $\ell$'s satisfying $\sum_j jk_j=\sum_j j\ell_j=n$. This amounts to the square of the $n$-the Taylor coefficient of $e^{nz}e^{nz^2}e^{nz^3}\dots=e^{\frac {nz}{1-z}}$. The Cauchy bound with the radius $1/2$ (yeah, one can optimize here, but we have already missed our chance for the exact asymptotics when deciding to separate the orders, so why to care now?) gives $(2e)^{2n}$ and the final estimate of 
$$
\frac{(2n)!}{n^n}(4e^2)^n=n!e^{O(n)}
$$
The end :-)
A: One term you might want to search is "interval order" https://en.m.wikipedia.org/wiki/Interval_order
If you fix the interval lenghts it might be open. Not the expect. One time, in an unrelated search I found this 
Bousquet-Mélou, Mireille; Claesson, Anders; Dukes, Mark; Kitaev, Sergey (2010), "(2+2) free posets, ascent sequences and pattern avoiding permutations", Journal of Combinatorial Theory, Series A, 117 (7): 884–909, MR 2652101, doi:10.1016/j.jcta.2009.12.007
A: 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.
