Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.


I have seen several times the use of "n choose k" in the left side of the permutations formula.
However, this expression is usually referred to be used with combinations.
Not that this change when or how using "permutations" or "subsets" according to the context.
But I wonder why the binomial coefficient is used in permutations context.
Thanks.

Permutation:
$$ (π‘›Β¦π‘˜)=𝑛!/(π‘›βˆ’π‘˜)! $$ Combination:
$$ (π‘›Β¦π‘˜)=𝑛!/π‘˜!(π‘›βˆ’π‘˜)! $$

share|improve this question

1 Answer 1

up vote 2 down vote accepted

For non-negative integers $n$ and $k$ the binomial coefficient $\binom{n}k$ is the number of $k$-sized subsets of a set of $n$ things: it’s the number of different combinations of $k$ of the $n$ elements. The members of a $k$-sized set can be listed in $k!$ different orders, so there are altogether $k!\binom{n}k$ permutations of $k$-sized subsets of the original set of $n$ things, $k!$ orderings of each of $\binom{n}k$ sets.

But $\dbinom{n}k=\dfrac{n!}{k!(n-k)!}$, so $$k!\binom{n}k=k!\cdot\frac{n!}{k!(n-k)!}=\frac{n!}{(n-k)!}=n(n-1)(n-2)\dots(n-k+1)\;,$$

and you often see the formula for the number of permutations of $k$-sized subsets of an $n$-set expressed in one of these last two ways instead of as $k!\binom{n}k$. In some ways these are simpler than the form $k!\binom{n}k$. However, because the binomial coefficients turn out to be rather easy to work with, and because many relationships involving them are known, it’s often convenient to write the number of permutations as $k!\binom{n}k$ in order to take advantage of those known relationships.

share|improve this answer
    
Thank you Brian! Nice explanation. –  Diego Oct 25 '12 at 19:10
    
@Diego: Thanks! You’re welcome. –  Brian M. Scott Oct 25 '12 at 19:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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