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

$\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.

• Note that $$\frac{n!}{(n-k)!} = (n-k+1) \cdot \dots \cdot n = \prod_{i=n-k+1}^n i$$ – Tacet Dec 3 '14 at 0:42
• Look at your method: $8\times 7\times 6\times 5\times 4$ is the same as $\frac{8!}{3} = \frac{8\times 7\times 6\times 5\times 4\times 3\times 2\times 1}{3\times 2\times 1}$. The idea is to represent $n(n-1)(n-2)...$ in terms of factorials. – Michael M Dec 3 '14 at 0:42

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
ba|cd     ba|dc
bd|ac     bd|ca
ca|bd     ca|db
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.

• Try on your own with $k\ne n-k$ if you still need to be convinced. – Yves Daoust Dec 3 '14 at 10:20

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)!}$$

• Ok, thanks +1. But I don't understand why you are dividing...how does a sequence of multiplication lead to division? – Emi Matro Dec 3 '14 at 1:52
• @user437158, see my edited answer. – lhf Dec 3 '14 at 9:53

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.

• This is correct logic, but may be a bit circular. The binomial coefficient can be derived from the permutation formula. So we start with $P(n, k) = n!/(n-k)!$. We then divide out by the Symmetry group on the $k$ elements (the group of permutations) to get $\binom{n}{k} = P(n, k) = \frac{n!}{ |S_{k}| (n-k)!} = \frac{n!}{k! * (n-k)!}$. – ml0105 Dec 3 '14 at 0:51