¿Conexión de puntos al azar en un círculo?

Question

Esta pregunta surgió como yo estaba tratando de encontrar una variante más simple de mi aguja problema.

---

Yo le fueron uniformemente, de forma aleatoria y establecer independientemente $2n$ puntos en un círculo, y luego al azar de conectar de una manera tal que cada punto tiene su propio par, ¿cuáles serían las probabilidades de encontrar a $k$ intersecciones?

---

Basada en el máximo número de intersecciones podemos ver que si $k \gt \frac{n(n-1)}{2}$, $P=0$. Por otra parte tenemos a algunos de los $P>0$.

Al conectar los puntos, todo lo que importa es el orden de los puntos.

---

El Análisis De Los Datos

Puedo escribir $P(n,k) = a / b$.

A continuación, $b$ es el número de maneras para conectar los puntos de forma única, y $a$ es el número de casos con $k$ intersecciones para $n$ líneas.

Hay $b = (2n-1)!!$ formas de conectar los puntos de forma exclusiva.

Me escribió una pieza de código en java para tratar de fuerza bruta soluciones de $a$$n$$10$.

Yo les escribí en una hoja de cálculo como una imagen. Aquí está la raw de datos como texto.

Después de cerca el análisis de los valores de $a$, OEIS me proveyó de una secuencia. Se ve como alguien ya ha calculado $a$, lo que en realidad es el número de maneras de organizar las n acordes en un círculo con k simple intersecciones.

Luego, si nos fijamos en el ejemplo, podemos elegir el $n$th fila y $k$ésima columna de la plaza de la tabla en A067310 para obtener el $a(n,k)$:

k = 0,1,2,3,4,5,6,...;

    1,0,0,0,0,0,0,...; n = 0
    1,0,0,0,0,0,0,...; n = 1
    2,1,0,0,0,0,0,...; n = 2
    5,6,3,1,0,0,0,...; n = 3
    ...              ; n = ...

Así

$$P(n,k)=\frac{a(n,k)}{(2n-1)!!}$$

Que iba a solucionar mi problema.

---

Me las arreglé para calcular la respuesta al problema inicial, pero tengo una pregunta adicional con respecto a la solución.

Yo no entiendo muy bien cómo fue esta secuencia calculada (aparte de de la computación). Veo que hay una fórmula que funciona si me conecte $k=0$ y cualquier otro $n$, pero las necesidades de los diferentes desplazamientos para cada uno de los diferentes $k>0$? ¿Cómo fue que derivó en el primer lugar? (También, si usted mira la fórmula, no hay "yo" en lugar de "k"? Creo que es un error tipográfico así que me lo reemplazó con $k$)

$$\sum_{j=0}^{n-1} (-1)^j \times \binom{(n-j)\times(n-j+1)/2-1-k}{n-1} \times\left(\binom{2n}{ j}-\binom{2n}{ j-1}\right)$$

Answer 1

La fórmula que se encuentra en OEIS no parece ser correcto. No sé cómo derivar una fórmula para su problema, pero puedo presentar una válida de la fórmula que he encontrado. Yo también la transforman en una fórmula que podría ser más fácil.

La OEIS página en la que te dan enlaces a otros OEIS página, que contiene más información. El valor de $a(n, k)$ se calcula mediante el cálculo de los coeficientes de la serie de Taylor de una función. No tengo idea de cómo se les ocurrió esto. $$ \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} $$ Podemos calcular las derivadas: $$ \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} $$ Así que la fórmula completa se convierte en: $$ 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)!!} $$