Chapter 1: Basic Concepts
Permutations and Factorials
If we have n distinct objects to arrange in a row, and order of placement matters, we can arrange these things in n! different ways.
For the first object, we have n choices of places to put it. For the second object, we have n-1 choices of places to put it. And so on.
In general, if we have to choose k objects out of n total, and arrange them in a row, we have the number of possibilities as:
The total number of permutations is
The process of constructing a permutation of n objects, given all permutations of n-1 objects, is important. If we consider the case of three objects ,
Here are permutations of order 3:
Now, how to get to permutations of 4 objects?
For each permutation of n-1 elements, form n additional permutations by inserting the nth element in every possible open slot
Adding 4 to our set of objects and using method 1 gives:
For each permutation of the n-1 elements, form n new permutations by first constructing the array:
Aaaaaand... yeah. No idea.
and with this convention,
for all positive integers n.
10! is a useful benchmark - it is around 3.5 million.
10! represents an upper ceiling on computable tasks.
To tell how large a very big factorial is going to be, use Stirling's formula:
Thus, for 8! = 40320:
Relative error of Stirling's formula is approximately
To obtain the exact value of n! factored into primes, we can use some useful identities. First, the prime p is a divisor of n! with multiplicity:
As an example, for n = 1000, p = 3,
Therefore, is divisible by , but not by .
Furthermore, to speed up the calculation of the above, we can use the identity
The Art of Computer Programmingnotes from reading Donald Knuth's Art of Computer Programming
Part of the 2017 CS Study Plan.
Volume 2: Seminumerical Algorithms
Volume 3: Sorting and Searching
Flags · Template:AOCPFlag · e