8
$\begingroup$

How can we prove that the number of ways choosing $k$ elements among $n$ is $\frac{n!}{k!(n-k)!} = \binom{n}{k}$ with $k\leq n$? This is an accepted fact in every book but i couldn't find a proof.

$\endgroup$
6
$\begingroup$

Well, let's first make sequences (ordered lists of distinct elements) of length $k$ from the $n$ element set.There are $n$ ways of picking the first element, $n-1$ ways of picking the second, ..., $n-k+1$ ways of picking the $k$th element. So there are $$n(n-1)\cdots (n-k+1) = \frac{n!}{(n-k)!}$$ such sequences.

But we want to count unordered lists, i.e., for each sequence, we want to identify the $k!$ permutations of its elements (each of which was counted separately above) as the same list. Hence the number of unordered lists is $$\frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{k!(n-k)!}.$$

$\endgroup$
  • 1
    $\begingroup$ I understand where the $\frac{n!}{(n-k)!}$ and $k!$ come from I just do not understand logically speaking why you divide the two to switch from ordered to unordered. (+1) $\endgroup$ – usainlightning Feb 26 '15 at 22:30
  • 2
    $\begingroup$ @usainlightning maybe try writing out all the ordered sequences for some small $n$ and $k$ and grouping them by those that have the same numbers. You will see that each group has $k!$ sequences, so dividing by $k!$ is like shrinking each group into one "element" (the set of numbers in the sequences in that group). Not sure if that makes sense $\endgroup$ – Casteels Feb 27 '15 at 7:02
  • 1
    $\begingroup$ @usainlightning another way to think about it: we have (# ordered sequences) = (#groups)(size of each group) where a group is the set of sequences with the same set of numbers. You want to count #groups and you have $\frac{n!}{(n-k)!}=$(# groups)$k!$. $\endgroup$ – Casteels Feb 27 '15 at 21:01
5
$\begingroup$

Notice that given $n$ objects $\{a_i\}$ and $n$ positions, there are $n$ possible positions for $a_n$. Once we have placed $a_n$, there are $n-1$ remaining positions for $a_{n-1}$. Once we have placed $a_n$ and $a_{n-1}$, there are $n-2$ positions left for $a_{n-2}$, and so forth. Thus, there are $$ n(n-1)(n-2)\cdots3\cdot2\cdot1=n! $$ possible ways to arrange the $n$ items.

Suppose we divide the $n$ items into $k$ white objects and $n-k$ black objects. For each arrangement of the white and black objects that looks the same, there are $k!$ rearrangements of the white objects and $(n-k)!$ rearrangements of the black objects. Since there are $n!$ rearrangements of the $n$ objects, there must be $$ \frac{n!}{k!(n-k)!}=\binom{n}{k} $$ arrangements of the $k$ white and $n-k$ black objects that look different.

$\endgroup$
3
$\begingroup$

Perhaps it will help you go over the permutation formula first $\frac {n!}{\left( n-k \right)!}$ and then thinking about the adaptation we need if we are to disregard order. It is easier this way.

$\endgroup$
2
$\begingroup$

First, for $k\leq n$ we must construct a $k$-permutation from an $n$-element set. We can choose the first item in $n$ ways, the second item in $n-1$ ways, whatever the choice of the first item,..., and the $k$th item in $n-(k-1)$ ways, whatever the choice of the first $k-1$ items. By the Multiplication Principle the $k$ items can be chosen in $n(n-1)\cdots (n-k+1)$ ways. We can rewrite this as $${n(n-1)\cdots (n-k+1)(n-k)!\over (n-k)!}={n!\over (n-k)!}.$$ Thus $P(n,k)={n!\over (n-k)!}$. By a $k$-permutation from a set $S$ of $n$ elements, we have an ordered arrangement of $k$ of the $n$ elements. Since we are concerned with the number of ways we can choose $k$ of the $n$ elements we want the number of unordered arrangements (subsets). Since each arrangement has length $k$ we can permute them in $k!$ ways. So the number of unordered arrangements of the elements of S is ${n!\over k!(n-k)!}$. Thus for $k\leq n$ $$C(n,k)={n!\over k!(n-k)!}.$$

$\endgroup$
1
$\begingroup$

if you have $k$ number of black and $n-k$ white balls what is your change of getting 1 white then 1 black then 1 white... it is $\frac{(n-k)!k!}{n!}$ and if your change of getting $1$ combination is $\frac{(n-k)!k!}{n!}$ how many combinations are there answer is $\frac{n!}{(n-k)!k!}$.this is how i think it but it can be flawed.

$\endgroup$

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.