How was "Number of ways of arranging n chords on a circle with k simple intersections" solved? The problem whose solution is based on the solution to the problem in the title came up as I was trying to find a simpler variant of my needle problem.


I we were to uniformly, randomly and independently set $2n$ points on
  a circle, and then randomly connect them in a way such that each point
  has its own pair, what would be the odds of finding $k$ intersections?


Based on the maximum number of intersections we see that if $k \gt \frac{n(n-1)}{2}$, $P=0$. Otherwise we have some $P>0$.
When connecting the points, all that matters is the ordering of points.

Data Analysis
I can write $P(n,k) = a / b$.
Then $b$ is the number of ways to connect the points uniquely, and $a$ is the number of cases with $k$ intersections for $n$ lines.
There are $b = (2n-1)!!$ ways of connecting the points uniquely.
I wrote a piece of code in java to try to brute-force solutions of $a$, for $n$ up to $10$.
I wrote them out in a spreadsheet as a image. Here is the raw data as text.
After closely analyzing the values of $a$, OEIS provided me with a sequence. Looks like someone already calculated $a$ which actually is the number of ways of arranging n chords on a circle with k simple intersections. 
But the given formula is not correct given as it is.

Thanks to Paul for fixing up a valid formula, since the OEIS one I stumbled upon seems to be wrong.

The formula for $P(n,k)$ then is:
$$ \frac{\displaystyle \sum_{j=1}^{\left\lfloor \tfrac12 +
 \tfrac12\sqrt{1+8k} \right\rfloor} (-1)^j \cdot
 \binom{n+k-1-\binom{j}{2}}{n-1} \cdot  \left( \binom{2n}{n+j} -
 \binom{2n}{n+j-1} \right)}{(2n-1)!!} $$
Which solves my initial problem.
But I'm still curious to know how someone came up with this in the
  first place, starting out with just a circle and some cords? Regarding the title; How was "Number of ways of arranging n chords on a circle with k simple intersections" solved to produce the expression in the numerator?

 A: The formula you found on OEIS doesn't seem to be right. I don't know how to derive a formula for your problem,
but I can present a valid formula I found. I will also transform it into an other formula that might be easier.
The OEIS page you give links to an other OEIS page, which contains more information. The value $a(n, k)$ is calculated by calculating the coefficients of the Taylor series of a function. I have no idea how they came up with this.
$$
\begin{eqnarray}
f_n(q) &=& (1-q)^{-n} \cdot \sum_{j=-n}^n (-1)^j \cdot \binom{2n}{n+j} \cdot q^{j(j-1)/2} \\
a(n, k) &=& \frac{{f_n}^{(k)}(0)}{k!}
\end{eqnarray}
$$
We can calculate the derivatives:
$$
\begin{eqnarray}
g_n(q) &=& (1-q)^{-n} \\
{g_n}^{(k)}(0) &=& \frac{(n+k-1)!}{(n-1)!} \\
h_n(q) &=& \sum_{j=-n}^n (-1)^j \cdot \binom{2n}{n+j} \cdot q^{j(j-1)/2} \\
{h_n}^{(k)}(0) &=& \sum_{j=-n}^n (-1)^j \cdot \binom{2n}{n+j} \cdot k! \cdot 0^{j(j-1)/2-k} \\
{f_n}^{(k)}(q) &=& \sum_{i=0}^k \binom{k}{i} \cdot {g_n}^{(k-i)}(q) \cdot {h_n}^{(i)}(q) \\
s(k) &=& \left\lfloor \tfrac12 + \tfrac12\sqrt{1+8k} \right\rfloor \quad\text{(inverse of } j(j-1)/2 \text{ )} \\
{f_n}^{(k)}(0) &=& \sum_{i=0}^k \binom{k}{i} \cdot \frac{(n+k-i-1)!}{(n-1)!} \cdot
\sum_{j=-n}^n (-1)^j \cdot \binom{2n}{n+j} \cdot i! \cdot 0^{j(j-1)/2-i} \\
&=& \sum_{j=1-s(k)}^{s(k)} \binom{k}{j(j-1)/2} \cdot \frac{(n+k-j(j-1)/2-1)!}{(n-1)!} \cdot
(-1)^j \cdot \binom{2n}{n+j} \cdot (j(j-1)/2)! \\
&=& k! \sum_{j=1-s(k)}^{s(k)} (-1)^j \cdot \binom{n+k-j(j-1)/2-1}{n-1} \cdot
 \binom{2n}{n+j} \\
\end{eqnarray}
$$
So the complete formula becomes:
$$
P(n,k) = \frac{\displaystyle \sum_{j=1}^{\left\lfloor \tfrac12 + \tfrac12\sqrt{1+8k} \right\rfloor} (-1)^j \cdot \binom{n+k-1-\binom{j}{2}}{n-1} \cdot
 \left( \binom{2n}{n+j} - \binom{2n}{n+j-1} \right)}{(2n-1)!!} 
$$
