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$
2
  • $\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, 2014 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, 2014 at 0:42

3 Answers 3

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$
2
  • $\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, 2014 at 1:52
  • $\begingroup$ @user437158, see my edited answer. $\endgroup$
    – lhf
    Dec 3, 2014 at 9:53
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$
1
  • $\begingroup$ Try on your own with $k\ne n-k$ if you still need to be convinced. $\endgroup$
    – user65203
    Dec 3, 2014 at 10:20
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$
1
  • $\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, 2014 at 0:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .