Proof For Combination Formula: N choose K I have been looking at this problem for a long time. Can anyone prove the combination formula using factorials N choose K? 
In case anyone does not know how to list all combinations in a set, you start with a permutation tree (for example)
1       2           3         4
234   134    124   123
You then delete all connected groups in the second row that are less than the previous row (or experience an inversion) which are in bold above.
 A: I copied my answer from Quora which I wrote on the same day as I saw this.
Let’s take the numbers 1 2 3 4 5 6 7 8 9 10 11 and call it set A
Ask yourself: how many ways can I make triplets from A (e.g. 1 2 3 or 10 11 6), where triplets with exactly the same numbers  count as one (e.g. 1 2 3 and 3 2 1)
Let’s start off by considering the number of different ways of ordering three numbers (permutations) from set A.
We start off with 11 options, followed by 10 left and then we are left with 9.
So 11 * 10 * 9 = 990
Let’s define a set B, which contains all of the different orderings of triplets from A.
Consider ANY element in set B. Let’s call the numbers x y z.
Because set B is a set of permutations, it’ll also contain values:

*

*x z y

*y x z

*y z x

*z x y

*z y x

So our goal, is to remove all extra five elements from set B for all triplets x y z. Well we can do this.
We know there are 990 permutations in total. For each permutation, there are five others which contain exactly the same numbers.
So let p be a single triplet. There will be 6p of these in B (ignoring their order).
We know 6p = 990. Hence p = 165. So there are 165 unique triplets in B, which answers our first question.
There is one issue I didn’t raise: how did I know how many different ways there were of ordering x y and z? Well the simple answer is that it was fairly trivial to think up the different orderings, since there were only three numbers per ordering.
If there were more numbers (let’s call this number r), then the best way to calculate the number of different orderings would be
r(r-1)(r-2)…1, which is r!. (Each time we have one less choice until there’s only 1 left)
So we can say: the number of different triplet combinations from the set A is
$\frac{11*10*9}{3!}$
OK, from this, we can think of a more general formula.
If there are n items in a set, the number of ways we can group r items is
$\frac{n(n-1)(n-2)...(n-r+1)}{r!}$
OK, we still haven’t derived the general combinations formula, but we’re getting closer.
There is one other concept we’ve yet to raise:
If I take r items from a group of n items, then there will be n-r unique group of items left over from the items I didn’t take.
For example, with set A, if I take a unique triplet (ignoring any permutations) 1 2 3, then I also have a unique set of 9 numbers 4 5 6 7 8 9 10 11.
Or if I took the numbers 4 8 11, I’d also end up with the numbers 1 2 3 5 6 7 9 10.
Therefore:
The number of ways of taking r items from a group of n items, is the same as the number of ways of taking n-r items from a group of n items.
So let’s go back to that general formula, and let’s call it x:
$\frac{n(n-1)(n-2)...(n-r+1)}{r!} = x$
By the above rule, this also means the number of ways of taking n-r items is also x. So
$\frac{n(n-1)(n-2)...(r+1)}{(n-r)!} = x$
If we add this together we get:
$2x = \frac{n(n-1)(n-2)...(r+1)}{(n-r)!} + \frac{n(n-1)(n-2)...(n-r+1)}{r!} $
[Note: original answer had an (n-1) denominator in first addend]
Now via simple adding of fractions we can do:
$2x = \frac{r![n(n-1)(n-2)...(r+1)]}{r!(n-r)!} + \frac{(n-r)![n(n-1)(n-2)...(n-r+1)]}{r!(n-r)!} $
But wait.
Let’s take a closer look at our numerators:
1. r![n(n-1)(n-2)...(r+1)]

2. (n-r)![n(n-1)(n-2)...(n-r+1)]

Number 1 implies 1234…*r (r!), multiplied by (r+1)(r+2)…(n-2)(n-1)n. S0 isn’t this just another way of writing out n! ?
Number two implies 1234…(n-r) ( (n-r)! ) multiplies by (n-r+1)(n-r+2)…(n-2)(n-1)n. Isn’t this also n! ?
Therefore, we can simplify this and say
$2x =  \frac{n!}{(n-r)!r!} + \frac{n!}{r!(n-r)!} $
so $2x = \frac{2n!}{r!(n-r)!}  $
Therefore x = $\frac{2n!}{2r!(n-r)!} $ = $\frac{n!}{r!(n-r)!} $
That's one way of proving the formula.
A: This is how I see it. 
Say I have 10 slots and 10 digits that I want to know how many permutations the digits that I can form, the slots look like
_ _ _ _ _ _ _ _ _ _
on the first slot, i have 10 options to choose from, so 
[10] _ _ _ _ _ _ _ _ _
since the first slot is already occupied, i am left with having 9 options
[10] [9] _ _ _ _ _ _ _ _
and the third slot will only have 8 left and so on, giving
[10] [9] [8] [7] [6] [5] [4] [3] [2] [1]...So the number of 10-digit numbers I can make is 10x9x8x7x6x5x4x3x2x1, which is the definition of 10! 
However if i have the same 10 digits but i only have 3 slots then
[10] [9] [8] = 10x9x8, which is 10!/7! or 10!/(10-3)! which in general form would become the familiar nPr = n!/(n−r)!
now, among the permutations for [10] [9] [8], the 3 slots themselves can also be rearranged 3! times. to make it easier, let's name the 3 slots, A, B and C 
[10]-->slot A [9]--> slot B [8]--> slot C 
ABC, ACB, BAC, BCA, CAB, CBA are all considered the same when what you want is a combination. so to remove the redundancy, we divide the number of permutations of the digits by the number of redundancies, that is to say, the number of permutations of the slots.
for which you get nCr = (permutation of digits)/(permutation of slots)
note that permutation of slots is always rPr, which is r!
and thus you get nCr = nPr /r! = n!/[(n-r)!r!]
A: First choose $k$ elements among the $n$ elements in some order, which can be done in $n\cdot(n-1)\cdots (n-k+1)$ ways.
In this count, any group of $k$ elements have been counted $k!$ times, which you have to compensate for, giving
$$\frac{n\cdot(n-1)\cdots (n-k+1)}{k!} = \frac{n!}{k!(n-k)!}.$$
A: According to Sheldon Ross' A First Course In Probability,  $n(n − 1) · · · (n − k + 1)$ represents the number of ways in which $k$ items can be selected from $n$ items when we care about the order of selection. Notice then that each group of $k$ items is counted $k!$ times. Then the number of different groups of $k$ items that can be made from a set of $n$ items is:
$$
\frac{n(n-1)(n-2)...(n-k+1)}{k!}
$$
Now, note also that $n!$ can be expressed as $n(n-1)(n-2)...(n-k+1)\times(n-k)!$ Given this information, we can derive the combination formula by multiplying this equation by $1=\frac{(n-k)!}{(n-k)!}$, which gives:
$$
\frac{n(n-1)(n-2)...(n-k+1)}{k!}\times\frac{(n-k)!}{(n-k)!} = \frac{n!}{k!(n-k)!} = {n \choose k}
$$
A: To generate a set of all possible 3-digit numbers where each digit is different, we can use two approaches.
Approach A: Choose the digits one by one, starting with 10 options for the first digit, 9 options for the second digit, and 8 options for the third digit.
Approach B: Generate all possible unique unordered triplets of numbers ($combinations$), permute each triplet, and insert them into the resulting set B.
These two approaches generate the same set, since every element in A has a corresponding unique triplet in B that is permuted in all possible ways, and every element in B can be generated by the way that set A was initially generated.
$|A|=10\times9\times8$ and $|B|=combinations \times 3!$
Since $|A| = |B|$
$combinations = \frac{10\times9\times8} {3!}$, or in general $combinations =\frac{n!}{(n - k)! \times k!}$
