Puzzle: How Many Possibilities Are There Between Connected Points? Puzzle
Jenny drew on her page six points, as shown below:

Jenny wants to build a cool match of her points. In a match , divide the six-point into pairs, so that each point has one partner exactly. Afterwards, each pair will be connected with a line. The condition that the match is called "cool match" the connected lines of the pairs must not cut each other, then the match is called a "cool match" . Jenny found that for her 6 points, there are five "cool matches" possible:

Danny Drew on his Page 12 points, as shown below:

How many "Cool matches" are possible in Danny's 12 points?
Bonus: Same Puzzle.
What will be the answer (how many possible "cool matches") are there for a drawing of 50 points?
Another Bonus: How many possible "cool matches" are there for a drawing of 1,000,000 (1 Million) Points? This will be a big number, just write its remainder when dividing it by 1,000,000,007 (Billion and seven).
 A: According to Wikipedia, the number of cool matches on $2n$ vertices is given by the $n_{th}$ Catalan number. No proof is given, but it's not too hard to cook up a proof.
Let $S(n)$ denote the number of cool matches on $2n$ vertices. Clearly $S(1) = 1$. By convention, lets say $S(0) = 1$ as well. 
Suppose we want to calculate $S(n)$. Choose one of the vertices and call it vertex $a$. Which vertices can vertex $a$ pair with? If vertex $a$ pairs with a non-adjacent vertex then it will split the circle into two regions. All other pairs must be contained within one and only one region. The pair with vertex $a$ will block pairs from crossing from one region to the other. 
Now, vertex $a$ can only pair with another vertex in such a way that each of the regions formed contains an even number of vertices. Otherwise we could not form a cool match since we would necessarily have unpaired vertices. If there are $2k$ vertices in one region, then there must be $2n-2k-2$ in the other region. 
How many pairs can form in each region? Well this just reduces to the same problem for a smaller $n$. $S(k)$ pairs can form in the first region and $S(n-k-1)$ pairs can form in the second region. Thus if vertex $a$ pairs with another vertex in such a way that there are $2k$ vertices in one region formed and $2n-2k-2$ vertices in the other region formed, then there are $S(k)S(n-k-1)$ ways to pair the remaining vertices.
Now if vertex $a$ pairs with an adjacent vertex, there will be only one region formed with $2n-2$ vertices. Thus there will be $S(n-1) = S(n-1)S(0)$ ways to pair the remaining vertices. Summing over all the possibilities for pairing vertex $a$ we have
$$S(n) = \sum_{k=0}^{n-1}S(k)S(n-k-1)$$
Recognizing this as the recurrence for the Catalan Numbers, we see that $S(n)$ is the $n_{th}$ Catalan number.
Thus 
$$S(n) = \frac{1}{n+1}{2n \choose n}$$
To compute the remainder of $S(500000)$ when dividing by 1,000,000,007. Use the alternative representation
$$S(n) = \prod_{k=2}^{n}\frac{n+k}{k}$$. Then use a generalization of memory efficient modular exponentiation. The Python code I had initially was incorrect, because the accumulation of floating point round off errors would lead to an incorrect answer. Instead use the fact that 
$$\left(\frac{a}{b} \mod p\right) = \left(a \mod p\right) \left(b^{-1} \mod p\right) \mod p$$
where $b^{-1}$ is the modular inverse of $b$ modulo $p$. $b^{-1}$ is the unique natural number $x$ with $0 \leq x < p$ such that $(a \mod p) * (b \mod p) \mod p = 1$. Here I've used mod in the programming language sense, rather than the mathematical sense. That is $a \mod b$ is the remainder when $a$ is divided by $b$. In many programming languages it is denoted by $a\; \%\; b$. 
If $p$ is prime then $b^{-1} = b^{p-2} \mod p$, this follows from Fermat's little theorem. Thus for $p$ prime, $b^{-1}$ can be computed using a memory efficient modular exponentiation algorithm, such as one of the ones I linked to.
We seek to calculate 
$$\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$ can be computed with a generalization of the memory efficient modular exponentiation algorithm. Once you understand the exponentiation case, you should be able to see how to modify it. 
$(k!)^{-1} \mod p$ can be computed in the same manner after noticing that
$$(k!)^{-1} = \prod_{j=1}^{k}k^{-1}$$
This algorithm is not too efficient though, but it will handle the case you see to compute. For more help I suggest asking on Stackoverflow, where there are probably people who can explain such things better and someone should be able to find a more efficient algorithm.
