# Faster way of calculating how many ways can $2n$ elements be paired?

So the problem is in how many ways $2n$ elements can be paired, my approach was multiply all odd numbers less then $2n$.

$(2n-1)*(2n-3)*...*1$ but my professor claimed it can be done much faster in algorithmic sense, but I don't really see the way to do so. Any hints? Thanks!

• The number $(2n-1)\cdot (2n-3)\cdots 3\cdot 1$ is known as the "double factorial" of $2n-1$, and written $(2n-1)!!$. But knowing that didn't help me find an answer to your question! – David Richerby Jun 30 '16 at 17:15
• Perhaps your professor meant the formula $(2n)!/(2^n n!)$, though I'm not sure why this is faster. – Yuval Filmus Jun 30 '16 at 20:25
• Adding to Yuval's answer, it's also equal to $\frac{n!}{2^n}\binom{2n}{n}$, but again that's not particularly better (worse, in fact). – Rick Decker Jul 1 '16 at 0:50
• – D.W. Jul 1 '16 at 3:56
• It is better, it changes $m$ subtractions into one bitshift and there is a trick to cut number of multiplications by half. – Evil Jul 1 '16 at 4:06

There is one algorithmic improvement if $n$ is large and you want to express this number for example as a decimal or binary number without any rounding errors: Let's say you have $n$ equals one billion. You will do about 500 million multiplications, and if you do this in a straightforward way, you will multiply various numbers from 1 to a bit over 4 billion digits by some small number. Multiplying an $n$ digit number by a small number takes $O(n)$ steps, so your product all in all takes $O(n^2)$ steps.
It's faster if you calculate 250 million products of up to 9 digit numbers giving 250 million 18 digit numbers, then 125 million products of 18 digit numbers giving 36 digit numbers and so on, until finally you multiply two numbers of 2 billion digits each. Multiplying $k$ digit numbers can be done in $O (k \log k)$ instead of $O (k^2)$, and therefore the total work is $O (n \log^2 n)$.
A completely different improvement for large $n$ is to use the Stirling approximation $n! \approx n^n \mathrm{e}^{-n} (2\pi n)^{1/2}$, and substitute that in the formula in Yuval's comment. Obviously that gives an approximation only.
• This gets a bit confusing because you use $n$ to mean different things even within the same paragraph. ("$n$ is large" seems to refer to the number whose double factorial we wish to compute but they you say "$n$ digit number") – David Richerby Jul 1 '16 at 15:12