Binomial Coefficient Factorial Derivation

[Odious Suspect]

A few decades ago my algebra teacher showed how to construct the expression for binomial coefficients. If I start with Pascal's recursion, and propose C(n,k)=n!/k!(n-k)!, I can prove it to be so through induction. But that doesn't give me that happy feeling that comes with understanding.

It can't be that hard; so I'm feeling really dumb at this point. How does one build up the relationship C(n,k)=n!/k!(n-k)! from scratch?

 

[fresh_42]

Is your $C(n,k)$ the number in Pascal's triangle at position $(n,k)$ or the number of combinations of $k$ balls out of $n$?
I know it's the same. I ask for definition.

 

[PeroK]

If you have $n$ things and $k$ of them are one colour (white, say) and the remaining $n-k$ of them are another colour (black), then there are $\frac{n!}{k!(n-k)!}$ ways to arrange them.

To see this, imagine they are numbered $1 - n$. The total number of ways of arranging them is $n!$. But, how many are the same black/white pattern - ignoring the numbers and looking just at the colour?

First, the $k$ white things can be put in any order - that's $k!$ - without changing the white/black pattern. And, the $n-k$ black things can likewise be re-arranged in any order without changing the pattern.

The total number of white/black patterns is, therefore, $\frac{n!}{k!(n-k)!}$

Now, think of the $n$ objects (all black, say), numbered and in order. We want to pick any $k$. This is what $\binom{n}{k}$ means: how many ways to choose $k$ objects from $n$.

If we do this by marking the ones we choose as white, then we see that every choice corresponds to a black/white pattern and vice versa. And, therefore, we have:

$\binom{n}{k} = \frac{n!}{k!(n-k)!}$

 

[fresh_42]

I'm still not sure whether I understood you. Say you have n numbered balls which k of them are black and white the rest. There are n! ways to order them. If you now decide to just look at the colors you have to divide by the k! orderings of black balls and (n-k)! orderings of white balls.
There are plenty of stories about this triangle. Some are here: http://www.mathsisfun.com/pascals-triangle.html
Ok, the page looks a bit childish. Nevertheless it might give you a kind of intuition.

 

[Odious Suspect]

iB=\left\{b_1,b_2,\ldots ,b_n\right\},\text{Null}b_i=T|F

B_j=\left\{b_{j_1},b_{j_2},\ldots ,b_{j_n}\right\} is the $j^{\text{th}}$ permutation of $B$, so $B_0=B$.

$A\left(B_j\right)$ is an arrangement of $B$ such that A\left(B_j\right)=A\left(B_k\right) means \left\{b_{j_1},b_{j_2},\ldots ,b_{j_n}\right\}=\left\{b_{k_1},b_{k_2},\ldots ,b_{k_n}\right\}. That is to say, T=b_{j_i}=b_{k_i} or F=b_{j_i}=b_{k_i}

B=C[B,k]\Rightarrow b_1=b_2=,\ldots ,=b_k=T\land b_{k+1}=b_{k+2}=,\ldots ,=b_n=F

P(B,j)=B_j is the transformation from B to B_j

Let A_q=A(P(B,q))=A\left(B_q\right) where q is the smallest permutation index for permutations with the same arrangement.

The number of arrangements A_q for a given C[B,k] is \left(\begin{array}{c} n \\ k \\ \end{array} \right).

If A(B)=A\left(B_m\right) then A(P(B,j))=A\left(P\left(B_m,j\right)\right)

To find the number of arrangements we divide the total number of permutation by the number of permutations satisfying A\left(B_j\right)=A_0

The total number of permutations of B is n!. The number of permutations satisfying A(C[B,k]) is the number of permutations of \left\{b_1,b_2,\ldots ,b_k\right\} times the number of permutations of \left\{b_{k+1},b_{k+2},\ldots ,b_n\right\}. That is k! (n-k)!.

Unfortunately, the library is closing, so this is fire and forget. I don't have time to proof it.

 

[Odious Suspect]

I have to admit, I cheated. This gave me the nudge that got me started.