0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Note that $$ \frac{n!}{(n-k)!} = (n-k+1) \cdot \dots \cdot n = \prod_{i=n-k+1}^n i$$ $\endgroup$ – Tacet Dec 3 '14 at 0:42
  • 2
    $\begingroup$ 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. $\endgroup$ – Michael M Dec 3 '14 at 0:42
2
$\begingroup$

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.

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

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

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

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.

$\endgroup$
  • $\begingroup$ 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)!}$. $\endgroup$ – ml0105 Dec 3 '14 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.