De acuerdo a Wikipedia, el número de enfriar los partidos en $2n$ vértices está dada por la $n_{th}$ catalán número. Ninguna prueba es dada, pero no es demasiado duro para cocinar una prueba.
Deje $S(n)$ denotar el número de enfriar los partidos en $2n$ vértices. Claramente $S(1) = 1$. Por convención, que permite decir $S(0) = 1$.
Supongamos que queremos calcular el $S(n)$. Elija uno de los vértices y la llamaremos vértice $a$. Que los vértices pueden vértice $a$ par? Si el vértice $a$ parejas con un no-vértice adyacente a continuación, se divide el círculo en dos regiones. El resto de los pares debe estar contenida dentro de una única región. A la par con vértice $a$ le pares de bloques de cruzar de una región a otra.
Ahora, vértice $a$ sólo puede emparejar con otro vértice de tal manera que cada una de las regiones formado contiene un número par de vértices. De lo contrario no podríamos formar un fresco partido desde que necesariamente tienen vértices impares. Si hay $2k$ vértices en una región, entonces no debe ser $2n-2k-2$ en la otra región.
Cuántas parejas se pueden formar en cada región? Bueno, esto sólo se reduce a el mismo problema para un menor $n$. $S(k)$ los pares se pueden formar en la primera región y $S(n-k-1)$ parejas se pueden formar en la segunda región. Por lo tanto, si el vértice $a$ parejas con otro vértice de tal manera que no se $2k$ vértices en una región formada y $2n-2k-2$ vértices en la otra región formado, entonces hay $S(k)S(n-k-1)$ formas para vincular el resto de los vértices.
Ahora bien, si el vértice $a$ parejas con un vértice adyacente, sólo habrá una región formada con $2n-2$ vértices. Por lo tanto habrá $S(n-1) = S(n-1)S(0)$ formas para vincular el resto de los vértices. Sumando sobre todas las posibilidades de emparejamiento vértice $a$ hemos
$$S(n) = \sum_{k=0}^{n-1}S(k)S(n-k-1)$$
Reconociendo esto como la recurrencia de la catalana Números, vemos que el $S(n)$ $n_{th}$ catalán número.
Así
$$S(n) = \frac{1}{n+1}{2n \choose n}$$
Para calcular el resto de $S(500000)$ cuando se divide por 1,000,000,007. El uso de la representación alternativa
$$S(n) = \prod_{k=2}^{n}\frac{n+k}{k}$$. A continuación, utilice una generalización de memoria eficiente exponenciación modular. El código Python que yo tenía, inicialmente, era incorrecta, ya que la acumulación de punto flotante de redondear errores daría lugar a una respuesta incorrecta. En lugar de utilizar el hecho de que
$$\left(\frac{a}{b} \mod p\right) = \left(a \mod p\right) \left(b^{-1} \mod p\right) \mod p$$
donde $b^{-1}$ es el inverso modular de $b$ modulo $p$. $b^{-1}$ es el único número natural $x$ $0 \leq x < p$ tal que $(a \mod p) * (b \mod p) \mod p = 1$. Aquí he utilizado el mod en el lenguaje de programación sentido, más que el sentido matemático. Que es $a \mod b$ es el resto al $a$ se divide por $b$. En muchos lenguajes de programación se denota por a $a\; \%\; b$.
Si $p$ es primo, a continuación,$b^{-1} = b^{p-2} \mod p$, esto se desprende de Fermat poco teorema. Así, por $p$ prime, $b^{-1}$ puede ser calculada utilizando una memoria eficiente algoritmo de exponenciación modular, como uno de los que más he ligado.
Buscamos para calcular
$$\prod_{k=2}^{n}\frac{n+k}{k} \mod p = $$
$$\left(\prod_{k=2}^{n}(500,000+k) \mod p\right) * \left((k!)^{-1} \mod p\right) \mod p$$
$\left(\prod_{k=2}^{n}(500,000+k)\right) \mod p$ puede ser calculada con una generalización de la memoria eficiente algoritmo de exponenciación modular. Una vez que usted entienda la exponenciación caso, usted debería ser capaz de ver cómo modificarlo.
$(k!)^{-1} \mod p$ puede ser calculada de la misma manera después de ver que
$$(k!)^{-1} = \prod_{j=1}^{k}k^{-1}$$
Este algoritmo no es muy eficiente, pero que se manejan en el caso de que usted vea a calcular. Para obtener más ayuda sugiero pedir en Stackoverflow, donde probablemente hay personas que pueden explicar mejor las cosas y que alguien debe ser capaz de encontrar un algoritmo más eficiente.
