How to reason about the combinatorial term "$n$ choose $k$" (i.e., $\binom{n}{k}=\frac{n!}{k!(n-k)!}$) The combinatorial number is the number of picking $k$ unordered outcomes out of $n$ possible choices. In that setting, we have a set $A$ with $|A|=n$ and the combinatorial numbers is just really the number of subsets $S\subset A$ with $|S| = k$.
This number is
$$\binom{n}{k} = \dfrac{n!}{k!(n-k)!},$$
but how can we reason about this? How can we derive this formula? I've seem some people reasoning about this in the following way: the number of ways to choose permutations with size $k$ among $n$ objects is
$$n(n-1)\cdots (n-k-1) = \dfrac{n(n-1)\cdots (n-k+1)(n-k)\cdots 1}{(n-k)(n-k-1)\cdots 1} = \dfrac{n!}{(n-k)!},$$
then we have to divide by $k!$ to disconsider the order. Why is that? Why dividing by $k!$ we get the number of subsets of $A$ with size $k$?
 A: Comment: I'll outline one way of thinking about the equation in question and a way of proving it that will possibly shed some insight. Induction is not the best or most efficient method of proof here, but it is slightly interesting that $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ can be proved using induction where Pascal's Rule is actually applied at the very end of the proof, and the proof also gives justification for the combinatorial terminology "$n$ choose $k$" represented by $\binom{n}{k}=\frac{n!}{k!(n-k)!}$.

Patterns: 


*

*Lemma 1: A set with $n$ elements has $n$ subsets containing exactly one element whenever $n\geq 1, n\in\mathbb{Z}$.

*Lemma 2: A set with $n$ elements has $n(n-1)/2$ subsets containing exactly two elements whenever $n\geq 2, n\in\mathbb{Z}$.

*Lemma 3: A set with $n$ elements has $n(n-1)(n-2)/6$ subsets containing exactly three elements whenever $n\geq 3, n\in\mathbb{Z}$.


All three lemmas can be proved rather easily using induction. It is interesting to note the pattern that emerges in Lemmas 1-3. It appears that we can make a conjecture as to what the number of $k$-element subsets will be for a set with $n$ elements.

Theorem: A set with $n$ elements has
$$
\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!} = \frac{n!}{k!(n-k)!} = \binom{n}{k}
$$
subsets containing exactly $k$ elements whenever $0\leq k\leq n$, and $n,k\in\mathbb{Z}$. 
Proof. When $n=0$, the only possible choice for $k$ is $k=0$, and when $n=k=0$, $\binom{0}{0} = 1$. This is true because the number of zero-element sets in a zero-element set is 1 (i.\,e., $\emptyset \subseteq \emptyset$). Lemmas 1-3 satisfy the cases when $n=1,2,3$, respectively. The proof proceeds by induction on $n$ of the statement $P(n):$ There are $\binom{n}{k}$ distinct $k$-element sets in a set with $n$ elements for every $k$ satisfying $0 \leq k \leq n$. 
Assume $P(\ell)$ is true for some $\ell \geq 3, \ell \in \mathbb{Z}$, and let $M$ be a set with $\ell+1$ elements. To show that $P(\ell) \rightarrow P(\ell+1)$, we must show that the number of $k$-element sets in $M$ is $\binom{\ell+1}{k}$ for every $k$ satisfying $0 \leq k \leq \ell+1$. When $k=0, \binom{\ell+1}{0}=1$, and when $k=\ell+1, \binom{\ell+1}{\ell+1} = 1$. Let $k$ satisfy $1 \leq k \leq \ell$, and fix some $\alpha \in M$. The number of $k$-element sets in $M$ that contains $\alpha$ is the number of sets with $k-1$ elements in $M \setminus \{ \alpha \}$; since $\left\vert{M \setminus \{ \alpha \}}\right\vert = \ell$, there are $\binom{\ell}{k-1}$ such sets by the inductive hypothesis. The number of sets with $k-1$ elements that do not contain $\alpha$ is $\binom{\ell}{k}$, also by the inductive hypothesis. Using Pascal's Identity, the number of $k$-element sets in $M$ is $\binom{\ell}{k-1}+\binom{\ell}{k} = \binom{\ell+1}{k}$.
Thus, the statement $P(n)$ is true for all $n \geq 0, n \in \mathbb{Z}$, and the Theorem holds by induction. $\blacksquare$

Added: The notation $\binom{n}{k}$ is sometimes introduced in combinatorics by first introducing the Pochhammer symbol, $n^{\underline{k}}$. An explanation of the above Theorem with a more combinatorial flavor (since your question is tagged combinatorics) may briefly proceed as follows: Let $A=\{1,2,\ldots,n\}$. For $k\leq n$, the injection $\{1,2,\ldots,k\}\to A$ is a $k$-element permutation. The number of $k$-element permutations of a set of size $n$ is given by
$$
n^{\underline{k}}=\prod_{i=0}^{k-1}(n-i)=n(n-1)(n-2)\cdot(n-k+1)=\frac{n!}{(n-k)!}.
$$
Since $\binom{n}{k}$ is by definition the number of $k$-element subsets of size $n$ and there are $k!$ ways to order a set of size $k$, we know that $n^{\underline{k}}=\binom{n}{k}\cdot k!$, and this implies that $\binom{n}{k}=\frac{n!}{k!(n-k)!}$. 
A: We have $n$ ways to choose the first element, then $n-1$ ways (one element is already removed) to choose the second element and .. $n-k+1$ ways (since the previous $k-1$ elements are already removed) to choose the last element (here the order the elements are chosen is important, since it matters which element is chosen first, second and so on). In other words, this procedure counts $(1,2)$ and $(2,1)$ as two distinct combinations of two elements. So it counts all $k!$ permutations of the same chosen elements as distinct (see below).
So this number is $n \times (n-1) \times (n-2) \times .. \times (n-k+1)$  $$= \frac{n \times (n-1) \times .. \times 1}{(n-k) \times (n-k-1) \times .. \times 1} = \frac{n!}{(n-k)!}$$ 
(by the definition of factorial)
Since order does not matter these $k$ numbers can be permuted in $k!$ ways (similar reasoning as above), so we have to divide by this number to discard the permutations. So the final result is:
$$\frac{n!}{k!(n-k)!} = {n \choose k}$$
To elaborate a little on this by an example, suppose we have the items $(a,b,c,d)$ and we wamt to choose two of them where order does not matter (i.e count both $(a,d)$ and $(d,a)$ as the same combination, meaning discard permutations).
We have $4$ ways to choose the first element which can be anyone lets say $a$. Then we have $3$ ways to choose the second element which lets say is $d$. But the same process can also count this scenario: the first element is $d$ and the second is $a$.
Another way to see the combinatorial coefficient (where order does not matter) is this:

We have $n$ ways to choose the first element and $k$ ways to place
  it in any position $1..k$, then $n-1$ ways (one element is already
  removed) to choose the second element and $k-1$ ways to place it in
  another position (one position is already taken) and .. so on

A: This might be verbose but bear with me, imagine you have a bag with $10$ marbles and you want to figure out all the ways you can pick the $10$ marbles out of the bag (so lists of 10 marbles in different combinations), for the sake of clarity imagine every one of those marbles have a unique color. In your first choice you have $10$ different marbles to choose from, let's say you pick pink, now you have $9$ different choices, but what if you originally picked orange, now you still have $9$ different choices. What this shows is that for every first marble you choose you have 9 more to go for, or in other words $10\times 9$ choices.  If we continue for the third marble we have 8 possible choices after we removed the second marble, so again we have $9\times 8$ choices but remember we had 10 groups of choices from the beginning, so in total we have $10\times 9\times 8$ choices. This goes on until you have 1 marble left in which case you have a total choice of $10 \times 9 \times 8 \times \cdots \times 1 = 10!$ possible choices for our bag of 10 marbles. Now let's say we actually only want to pick 4 marbles, not all 10. That means out of the possible $10!$ choices for all $10$ we only get $10\times 9\times 8 \times 7$ or equivalently:
$$\frac{10!}{(10-4)!} = \frac{10!}{6!} = 7\times 8\times 9\times 10$$
Possible choices. What if though, we don't care about the order of choice, so the marbles we do pick, we can label them as $R,G,B,Y$ order does not matter. So, $R,G,B,Y$ is equivalent to $R,B,G,Y$. So, if want to choose $4$ marbles from our bag of $10$ and we don't care about the arrangement of our elements we need to divide it by $4!$ which represents our number of ways to arrange $4$ elements, hence:
$$\frac{10!}{4!\cdot(10-4)!} = 210$$
