Combinations & Permutations

n! (factorial of n): —

The outer two never move; the middle two swap four times

Across every pair with r no larger than n up to 60, plain combinations are always the smallest of the four and n^r is always the largest. Neither ever changes place. The two in the middle do, and hardly ever: the multiset count beats the permutation count in exactly 4 of those pairs, and every one of them has r equal to n — the 2, 3, 4, 5. The last is 5 choosing 5, where 126 edges out 120 by six, and from 6 upward the falling factorial pulls away for good. There is also exactly one non-trivial tie in the range: 3 choosing 2, where both come to 6. (At r = 1 all four are just n, which ties everywhere for a boring reason.)

The textbook formula gets under a quarter of its answers right

Every combinatorics course writes C(n,r) as n! over r!(n−r)!. Compute it that way in ordinary floating point, across every pair with n from 0 to 200:

The middle group is the interesting one. C(55,24) is the first to go wrong and it comes out as 2488589544741301 when the answer is 2488589544741300 — one too many, with nothing about the number to suggest it. Wrong answers outnumber overflows by 1.8 to one.

The overflows are at least loud. They start at C(171,0), whose answer is 1 — the formula computes 171! before it does anything else, and 171! is larger than a double can hold.

The order of operations is the whole problem

C(200,100) is about 9 × 10⁵⁸. Large, and nothing an arbitrary-precision integer cannot hold. The trouble is that the textbook formula asks for 200! along the way, and 200! is three hundred digits larger than the answer it is being used to compute.

Building an enormous intermediate on the way to a modest result is the mistake, not the size of the result. This page multiplies the falling product instead — n × (n−1) × … × (n−r+1) — and divides by r!. That is still bigger than the answer, by a factor of r!, but it is around half the digits of the factorial route.

The division is whole-number division, which discards any remainder — alarming if a remainder were possible. It is not: r consecutive integers always contain a multiple of r, of r−1, and so on, so their product is always divisible by r!. Checked rather than assumed, across all 1,891 pairs with n up to 60: 0 had anything left over.

Where a double-precision factorial actually stops

Later than the safe-integer limit suggests. Whole numbers stay exact up to 9,007,199,254,740,991, which 21! passes comfortably — and 21! and 22! are still exact anyway, because a factorial gathers factors of two and the low bits it would lose are zeros. A double carries 53 significant bits, so a value of B bits needs B − 53 of its low bits to be zero.

The margin shrinks and runs out at exactly 23, which is why 23! is the first one that comes back wrong. This page uses arbitrary-precision integers and has no such limit; the scientific calculator elsewhere on this site uses doubles and does.

Which raises a display problem rather than an arithmetic one. Permutations of 5000 from 5000 is a 16,326-digit number, and printed in full with thousands separators it is 21,767 characters. All three results are now cut at sixty digits with the total appended, so a large answer says how large it is instead of filling the page.