Just by looking at formulas for Combinations (Binomial Coefficients), we are potentially talking about taking 1 astronomically large number and dividing it by two other not so astronomically large, just stupidly large, numbers. All that, just to get a number that is quite small in comparison.
Let’s start with a said formula.
\(
\begin{pmatrix}
n \\
k
\end{pmatrix}
=\frac{n!}{k!(n-k)!}
\)
Now for an example
\(
\begin{pmatrix}
40 \\
30
\end{pmatrix}
=\frac{40!}{30!\cdot 10!}
\approx \frac{8.1592\cdot 10^{47}}{2.6525\cdot 10^{32}\cdot 3628800}
\)
\(
\begin{pmatrix}
40 \\
30
\end{pmatrix}
=847660528
\)
I really don’t have the interest to deal with an integer that is 48 digits long in order to get a number that is not even 10 digits long. Of course, there are a lot of simplifications going on in there. We will need to do these simplifications as we go.
Breaking Things Down
Let’s take another look at the above example and write it in a way so we can make some simplifications
\(
\begin{pmatrix}
40 \\
30
\end{pmatrix}
=\frac{40!}{30!\cdot 10!}
\)
Let’s isolate a \(30!\) in the numerator and denominator.
\(
\begin{pmatrix}
40 \\
30
\end{pmatrix}
=\frac{40 \cdot 39 \cdots 32 \cdot 31 \cdot 30!}{10!\cdot 30!}
\)
Simplify the \(30!\)
\(
\begin{pmatrix}
40 \\
30
\end{pmatrix}
=\frac{40 \cdot 39 \cdots 32 \cdot 31}{10!}
\)
Expand the numerator and denominator
\(
\begin{pmatrix}
40 \\
30
\end{pmatrix}
=\frac{40 \cdot 39 \cdot 38 \cdot 37 \cdot 36 \cdot 35 \cdot 34 \cdot 33 \cdot 32 \cdot 31 }{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}
\)
Now lets take a moment to pause. The numerator is still quite large, \(\approx 3.08 \cdot 10^{15}\).
Take a leap of faith with me and we are going to rewrite as follows.
\(
\begin{pmatrix}
40 \\
30
\end{pmatrix}
=\frac{40}{1}\frac{39}{2}\frac{38}{3}\frac{37}{4}\frac{36}{5}\frac{35}{6}\frac{34}{7}\frac{33}{8}\frac{32}{9}\frac{31}{10}
\)
The Trick
We will now take advantage of consecutive numbers. If we were to take two consecutive numbers and multiply them together, we are guaranteed that this number has a factor of 2. Now if we do the same thing with 3 consecutive numbers, we would be guaranteed a factor of 2 as well as a factor of 3. This continues for any number of consecutive numbers.
Try to prove it to yourself.
So let’s take advantage of this and solve for our combination.
Start with 1. Multiply this by the largest element in the numerator and divide by the least in the denominator. Then multiply by the second largest element in the numerator and divide by the second least element in the denominator. So on and so forth till we have exhausted all elements in the numerator and denominator.
When done this way we will always get an integer after each division. See for yourself.
\(
\begin{matrix}
1 \cdot 40 &=& 40 \\ 40 \cdot \frac{1}{ 1 }&=& 40 \\ \hline
40 \cdot 39 &=& 1560 \\ 1560 \cdot \frac{1}{ 2 }&=& 780 \\ \hline
780 \cdot 38 &=& 29640 \\ 29640 \cdot \frac{1}{ 3 }&=& 9880 \\ \hline
9880 \cdot 37 &=& 365560 \\ 365560 \cdot \frac{1}{ 4 }&=& 91390 \\ \hline
91390 \cdot 36 &=& 3290040 \\ 3290040 \cdot \frac{1}{ 5 }&=& 658008 \\ \hline
658008 \cdot 35 &=& 23030280 \\ 23030280 \cdot \frac{1}{ 6 }&=& 3838380 \\ \hline
3838380 \cdot 34 &=& 130504920 \\ 130504920 \cdot \frac{1}{ 7 }&=& 18643560 \\ \hline
18643560 \cdot 33 &=& 615237480 \\ 615237480 \cdot \frac{1}{ 8 }&=& 76904685 \\ \hline
76904685 \cdot 32 &=& 2460949920 \\ 2460949920 \cdot \frac{1}{ 9 }&=& 273438880 \\ \hline
273438880 \cdot 31 &=& 8476605280 \\ 8476605280 \cdot \frac{1}{ 10 }&=& 847660528
\end{matrix}
\)
I will note that the multiplications did not need to be from highest to lowest. It could have been from lowest to highest. What was important was that they were in consecutive order. The divisions had to be from lowest to highest.
See
\(
\begin{matrix}
1 \cdot 31 &=& 31 \\ 31 \cdot \frac{1}{ 1 }&=& 31 \\ \hline
31 \cdot 32 &=& 992 \\ 992 \cdot \frac{1}{ 2 }&=& 496 \\ \hline
496 \cdot 33 &=& 16368 \\ 16368 \cdot \frac{1}{ 3 }&=& 5456 \\ \hline
5456 \cdot 34 &=& 185504 \\ 185504 \cdot \frac{1}{ 4 }&=& 46376 \\ \hline
46376 \cdot 35 &=& 1623160 \\ 1623160 \cdot \frac{1}{ 5 }&=& 324632 \\ \hline
324632 \cdot 36 &=& 11686752 \\ 11686752 \cdot \frac{1}{ 6 }&=& 1947792 \\ \hline
1947792 \cdot 37 &=& 72068304 \\ 72068304 \cdot \frac{1}{ 7 }&=& 10295472 \\ \hline
10295472 \cdot 38 &=& 391227936 \\ 391227936 \cdot \frac{1}{ 8 }&=& 48903492 \\ \hline
48903492 \cdot 39 &=& 1907236188 \\ 1907236188 \cdot \frac{1}{ 9 }&=& 211915132 \\ \hline
211915132 \cdot 40 &=& 8476605280 \\ 8476605280 \cdot \frac{1}{ 10 }&=& 847660528
\end{matrix}
\)
And there we have it. An easy way to calculate combinations while avoiding astronomically huge numbers (four gumdrops).
Recent Comments