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.

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 :-)

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