clarification on the formula $\frac{n!}{(n-k)!}$

Question

$\dfrac{n!}{(n-k)!}$ is used in order to find non-repetitive lists of length $k$ given $n$ possible symbols.

For example: find the number of non-repetitive lists of length five that can be made form the symbols $1,2,3,4,5,6,7,8.$ I understand that this can be solved by this method (multiplication principle): $8 \times 7 \times 6 \times 5 \times 4=6720$.

I don't understand this method of solving the problem: $\dfrac{8!}{(8-5)!}=\dfrac{8!}{3!}= \dfrac{40{,}320}{6}=6720$.I am having a hard time understanding this intuitively, why is $k$ subtracted from $n$ in the denominator? The subtraction gives $3!$ and that is not a factorial representing a length of five. It seems like this makes us find how many length of $3$ are there....

Thank you.

Answer 1

Consider the $n!$ permutationsof $n$ elements. They are all different. But you only care about the first $k$ elements, so the permutations that differ only in the order of the last $n-k$ elements (there are $(n-k)!$ of them) must be counted once only.

ab|cd     ab|dc 
ac|bd     ac|db 
ad|bc     ad|cb
ba|cd     ba|dc
bc|ad     bc|da 
bd|ac     bd|ca
ca|bd     ca|db
cb|ad     cb|da
cd|ab     cd|ba
da|bc     da|cb
db|ac     db|ca
dc|ab     dc|ba

In the example there are $4!=24$ permutations, each arrangement of two letters appearing $(4-2)!=2$ times (last $2$ letters ignored), hence after regrouping, $$\frac{4!}{(4-2)!}=\frac{4.3.2.1}{\ \ \ \ \ \ 2.1}=12.$$

Said differently, the division "undoes" the excess multiplies.

---

It is interesting to note that if you also don't care about the order of the first $k$ elements, you need to divide by $k!$ as well and obtain the fomula for combinations $$\frac{n!}{k!(n-k)!},$$ which, by some magic, always yields integer values.

Answer 2

It is well known that $$ \binom{n}{k}=\frac{n!}{(n-k)!k!} $$ gives the number of ways to choose $k$ items from a list of $n$ items. Now this does not take order into account. For example, if you have the numbers $1$, $2$ and $3$, and you want to choose two numbers between them, you will have $$ 1,2\\ 1,3\\ 2,3 $$ as possibilities. That's $\frac{3!}{1!2!}=3$ possibilities. The formula you give would be $2!$ times $3$, that is, $6$ possibilities. That takes the permutations of the $k$ elements into account. For each set of $2$ elements between the $3$ elements, you can permute the two elements in $2!$ fashions.

In general, if you want to know how many ways there are to take $k$ elements from a set of $n$ elements, taking order into account, you will have $$ \binom{n}{k}\times k! $$ choices, that is, $$ \frac{n!}{(n-k)!} $$ choices.

Answer 3

You have $n$ choices for the first element in the list, $n-1$ for the second, ..., $n-(k-1)$ for the $k$-th. So the number is $$ n \cdot (n-1) \cdots (n-(k-1)) = n \cdot (n-1) \cdots (n-(k-1)) \frac{(n-k)!}{(n-k)!} = \frac{n!}{(n-k)!} $$