Number of ways of selecting $k$-element subsets from an $n$-element set?

Question

I want to find the number of ways of selecting $k$-element subsets from an $n$-element set.

---

Suppose we select the elements one by one. There are $n$ ways of selecting the first one, leaving $n-1$ ways for the second, and so on, until we reach $n-k+1$ ways to select the $k$-th one, so there are:

$$n \cdot (n-1) \cdots (n-k+1)$$

ways. However, apparently we should divide by $k!$ Why? For what it's worth, I understand that we could select them two by two etc as well. I just don't understand how dividing by $k!$ fixes it all.

Answer 1

Dividing by $k!$ is needed because in your

$$n \cdot (n-1) \cdots (n-k+1),$$

you're actually permuting those $k$ element in a row. E.g. If you choose out

$$1,2,3$$

you will also count

$$1,3,2\\ 2,1,3\\ 2,3,1\\ 3,1,2\\ 3,2,1$$

since by your formula it just says $3\times2\times1=6,$ which includes all above shown, but they all represent the same set $\{1,2,3\}.$

Answer 2

Number of ways of selecting $k$ element subsets from an $n$ element set $$=\binom{n}{k}=\frac{n!}{(n-k)! \times k!}$$

$$=\frac{n \times (n-1) ...\times (n-k+1)\times(n-k)!}{(n-k)! \times k!}$$

$$=\frac{n \times (n-1) ...\times (n-k+1)}{ k!}$$

Further if you want to know why we are dividing it by $k!$ without knowing the proof,it is as follows.You have $n$ ways to select the first ,$n-1$ ways for second and ....(n-k+1) for the last one .but as you are multiplying it,all the cases (permutation) will be covered,to avoid from duplication we divide it by $k!$