3
$\begingroup$


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:
$$ (๐‘›ยฆ๐‘˜)=๐‘›!/๐‘˜!(๐‘›โˆ’๐‘˜)! $$

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you Brian! Nice explanation. $\endgroup$
    – Diego
    Oct 25, 2012 at 19:10
  • $\begingroup$ @Diego: Thanks! Youโ€™re welcome. $\endgroup$ Oct 25, 2012 at 19:15

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.