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?

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)!!} $$