Derivation of Permutation Formula

Question

I've been familiar with the formula of finding the $r$-permutation of an $n$-element set; but I've only been half-so familiar with deriving the formula. See, I know that to prove the truth of $$ P(n,r) = \frac{n!}{(n-r)!} $$

It is first conventional to show that $$ P(n,r) = n \times (n-1) \times (n-2) \times \cdots \times (n-r+1) $$ and this is exactly where I find myself struggling.

To construct all possible ways of choosing $r$ elements from an $n$ element set, we can reason accordingly: the first element can be chosen in $n$ different ways, the second element can be chosen in $(n-1)$ different ways ... and it is said to me that the $r$th element can be chosen in $n-(r-1)$ different ways. But I do not see why the last one stands. I can admire the pattern in which it makes sense. Since judging by the position of the element, the first element can be represented with $n-(1-1)$ (because it's in the first place), then second with $n-(2-1)$ (because it's in the second place), the third in $n-(3-1)$ (because it's in the third place), and finally the $r$th with $n-(r-1)$ (because it's in the $r$th place); but this pattern hasn't been concretely proven, and hence isn't it only merely a conjecture? Could anyone provide a good impermeable proof of this? Thank you in advance.

Answer 1

There are $r$ consecutive integers in the list $0, 1, \dots, r-1$ and these correspond to the $r$ factors by subtracting each from $n$.

---

In general, we have to be careful counting the number of integers in a discrete interval to avoid a fencepost error. For instance, for integers $a \leq b$, the number of integers $k$ satisfying $a \leq k \leq b$ is $b - a + 1$, which you is one more than the difference between the endpoints.

This formula yields the expected $r$ when applied to either $0 \leq k \leq r-1$ as I did above or the slightly more complicated expressions $n-r+1 \leq k \leq n$ that arises in the actual factors. It doesn't matter which one you count because they are in bijection with one another.

Answer 2

Okay, how many 4-digit numbers can you form with $1,2,3,4$ (without repetition)? Consider four blanks: $$----$$ There are four choices for the first blank, 3 for the second, 2 for the third and only 1 for the last. Thus, the total number of ways are $4 \times 3 \times 2 \times 1 = 4!$. What if there had been $7$ blanks and $7$ distinct digits? You would have $7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 7!$ ways. So, we understand that:
There are $n!$ ways to permute a list of $n$ objects if each object is distinct.

Let's get to the next level. What if you have 7 distinct digits, but only $4$ blanks (again without repetition)? Your strategy would be create $7$ blanks, and consider only the first $4$. But the trouble is: $$ 1 \space\space 2 \space\space 3 \space\space 4 \space\space 5 \space\space 6 \space\space 7$$ is the same as $$1 \space\space 2 \space\space 3 \space\space 4 \space\space 7 \space\space 5 \space\space 6$$ since you consider only the first $4$ blanks. So, you're overcounting. Keeping the first $4$ digits constant, how many times are we counting the same arrangement? That is just the number of ways to permute $7-4$ objects, or $(7-4)!$. You count every case $(7 - 4)!$ times, thus, the actual number of cases must be $\frac{7!}{(7-4)!}$. Generalising:
There are $\frac{n!}{(n-r)!}$ ways to permute $r$ objects out a collection of $n$ distinct objects.
Now that we've got the intuition, here's a formal proof:

Theorem : There are $\frac{n!}{(n-r)}$ ways of 'ordering' $r$ objects from a collection of $n$ distinct objects.
Proof: Consider $r$ blanks, to be filled by $r$ objects from the collection of $n$ distinct objects (repetition is not allowed). There are $n$ ways to choose the first. Since only $n-1$ objects are remaining, there are $n-1$ ways to choose the second. Generalising, there are $(n - k + 1)$ ways to choose the $k$th object. Thus, the total number of ways is given by $$\prod_{k = 1}^r (n-k+1)$$Simplifying: $$\frac{\prod_{k = 1}^n (n-k+1)}{\prod_{k = r+1}^n (n-k+1)}$$ $$\frac{n\times (n-1) \times ... \times 2 \times 1}{(n-r) \times (n - r - 1) \times ... \times 2 \times 1}$$ $$\frac{n!}{(n-r)!}$$ QED