I am confused regarding the derivation of the fact that, $${n \choose k} =\frac{n!}{k!(n-k)!}$$
I understand that the number of sequences of $n$ objects arranged $k$ ways is
$$\frac{n!}{(n-k)!}$$
and I also understand why there could be $n!$ different permutations of the same $n$ letters, but my question is:
In the formula, why does one divide by $k$! to get rid of such combinations? How does that remove them?
The number of sequences of length $k$ you can form from $n$ distinct objects is indeed $\frac{n!}{(n-k)!}$. But if you want to know the number of subsets of size $k$, you need to remove the multiple counting due permutations. That is, a subset of size $k$ can be organized into a sequence (ordered set) in $k!$ different ways, so the number of sequences is $k!$ as big as the number of subsets. You can remove multiple counting by the factor $k!$ by dividing that factor out.
Let us consider a concrete example. You have three objects called A, B and C, and you want to form subsets of size two (unordered pairs). In particular, you want to know how many unordered pairs you can form. There are six ordered pairs: AB, BA, AC, CA, BC, CB. Every unordered pair is counted twice ($2!=2$). That is, every unordered pair corresponds to two ordered pairs. To get rid of this double counting, you divide the number by two.
$\dbinom nk=\dfrac{n!}{k!(n-k)!} $ because, there are $n!$ ways to arrange n objects there are $(n-k)!$ ways to arrange the ones we don't choose and in combinations order doesn't matter. There are k! ways to arrange the $k$ objects we do choose, but again order doesn't matter so they are all counted as the same one. so in short, because we don't care about order, we can divide by the number of ways to arrange $k$ objects, and $n-k$ not chosen objects.
I also had troubles in mastering combinations, permutations and alike, so I am keen to expose the scheme I finally adopted to get through.
Consider first the number of ways to arrange a $k$-tuple out of $n$ different objects.
In a $k$-tuple the order is taken into account, and two $k$-tuples are considered different
if they have at least a pair of different objects, or if they have the same elements but placed in a different order.
You have $n$ choices for the element to pick and put as first, $n-1$ for the second, ..., up to $n-k+1$ for the k-th element.
Therefore you have $n(n-1)(n-2)\cdots(n-k+1)$ different ways to do that, i.e. there are $n(n-1)(n-2)\cdots(n-k+1)$ different possible $k$-tuples.
Clearly $n(n-1)(n-2)\cdots(n-k+1)=n!/(n-k)!$.
Then consider the number of ways to arrange $k$ different (labelled) objects into a row of $n$ labelled bins, where each bin can be empty or contain max one object. You distinguish the arrangements either because the empty-full sequence is different, or because the objects in the same bin are different. To put the first object you can choose among $n$ bins, for the second $n-1$ bins, ... and you end with the same number as before.
Now, if the order in which the objects are arranged in the $k$-tuple is not taken into account, i.e. you are considering $k$-subsets out of an $n$-set,
then it is clear that from each $k$-subset you can make $k!$ different $k$-tuples.
Therefore the number of $k$-subsets is $n!/(k!(n-k)!)={{n} \choose {k}}$.
In the same way, if you consider the arrangement into bins that differ only by the position of the objects in the row (the bin they are in), and not by the label of the object (i.e. the objects are undistinguishable), then it is evident that, by keeping firm the position of the objects and exchanging their labels , in $k!$ ways, you get the all the arrangements considered above, of $k$ distinguishable (labelled) objects into $n$ distinguishable (labelled) bins.
You divide by k! because there are k! possible permutations of k elements. This gives you just the number of combinations$\frac {1}{k!} ×$ $n (n-1)(n-2)... (n-(k-1)) $.
