Can $\frac{n!}{(n-r)!r!}$ be simplified?

Question

I'm trying to calculate in a program the number of possible unique subsets of a set of unique numbers, given the subset size, using the following formula:

$\dfrac{n!}{(n-r)!r!}$

The trouble is, on the face of it, you may need an enormous structure to hold the dividend (at least). Is there a way of simplifying this calculation, so that it can be calculated using something smaller like $64$-bit integers, or are you really going to have to store numbers like $60!$?

Alternatively, is there a formula that is more suited to computing the aforementioned value?

Answer 1

As mentioned by others, the binomial coefficient

$$\binom{n}{r}=\frac{n!}{r!(n-r)!}$$

is already so fundamental a quantity, that it is itself considered a canonical form. Nevertheless, you seem to be asking how one might compute this, while avoiding unsavory events like integer overflow.

Since this is for programming purposes, if you can stand to use a two-dimensional array, you might be interested in the doubly-indexed recurrence relation

$$\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$$

along with the initial conditions $\tbinom{n}{0}=\tbinom{n}{n}=1$, or the singly-indexed recurrences

$$\begin{align*} \binom{n}{r}&=\frac{n}{n-r}\binom{n-1}{r}\\ \binom{n}{r}&=\frac{n-r+1}{r}\binom{n}{r-1} \end{align*}$$

One other possibility is to instead deal with the logarithms of the factorials, since $\log(ab)=\log\,a+\log\,b$ and $\log(a/b)=\log\,a-\log\,b$. You might want to look into Stirling's formula if you want to take this route, but this is only intended for the cases where $n$ and $r$ are large.

Answer 2

Yes, the formula is nothing but $$\frac{n\cdot(n-1)\cdot...\cdot(n-r+1)}{1\cdot2\cdot...\cdot r} $$

This allows for easy calculation for values of $\;k\;$ up to $\;50\;$ or so.

Answer 3

It may depend on what is "simplified" for you. For example

$$\frac{n!}{(n-r)!r!}=\frac{(n-r+1)(n-r+2)\cdot\ldots\cdot n}{r!}=\frac{(r+1)(r+2)\cdot\ldots\cdot n}{(n-r)!}$$

Answer 4

For the purposes of a computer program, it's probably best to split it up unto $r$ different factors, each of which can be held in a standard double.

First assume without loss of generality that $2r<n$. If not, use the fact that ${n\choose r} ={n\choose n-r}$. This is obvious from the formula.

Now we have $$\begin{array}{rl} \frac{n!}{r!(n-r)!} &= \frac{1\times2\times\dots\times n}{(1\times2\times\dots\times r)(1\times2\times\dots\times n-r)} \\&= \frac{(1\times2\times\dots\times r)(r+1\times r+2\times\dots\times n)}{(1\times2\times\dots\times r)(1\times2\times\dots\times n-r)} \\ &=\frac{r+1}{1}\times\frac{r+2}2 \times \dots\times \frac{r+(n-r)}{r} \end{array}$$

So you may calculate the value of each fraction in a double and multiply them all quite easily. The answer you get should be an integer; if not you're losing precision somewhere.

Answer 5

To calculate $\binom{n}{r}$ with

• the least likelihood of overflow
• keeping any intermediate calculations as small as possible
• using only integers (no chance of involving even rationals),

use the following identity:

$$ \begin{array}{rcl} \binom{n}{r+1}&=&\frac{n-r}{r+1}\binom{n}{r-1} \end{array} $$

What this translates to is, in Pascal's triangle, moving along a row, starting from 1.

For example, to compute $$\binom{14}{4} = \frac{14\cdot13\cdot12\cdot11}{1\cdot2\cdot3\cdot4},$$ it is

$$ \begin{array}{ccc} 14*13&=&182\\ &&/2&=&91\\ &&&&\cdot12&=&1092\\ &&&&&&/3&=&364\\ &&&&&&&&\cdot11&=&4004\\ &&&&&&&&&&/4&=&1001\\ \end{array} $$

Since you're moving a long the row, you know that you'll be getting integers every time (you can always divide evenly). Also, you've computed other Pascal numbers along the way so you'll be more likely to remember them next time. What's $14 \choose 5$? Easy, multiply by $10/5$ to get $1001\cdot2$ or 2002.

This is also a manageable method for doing it in your head: easy sequence, low calculation overhead, fewer digits to remember.