Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binomial Coefficient Factorial Derivation

  1. Nov 18, 2015 #1
    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?
     
  2. jcsd
  3. Nov 18, 2015 #2

    fresh_42

    Staff: Mentor

    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.
     
  4. Nov 18, 2015 #3

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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)!}##
     
  5. Nov 18, 2015 #4

    fresh_42

    Staff: Mentor

    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.
     
  6. Nov 18, 2015 #5
    i[tex]B=\left\{b_1,b_2,\ldots ,b_n\right\},\text{Null}b_i=T|F[/tex]

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

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

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

    [itex]P(B,j)=B_j[/itex] is the transformation from [itex]B[/itex] to [itex]B_j[/itex]

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

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

    If [itex]A(B)=A\left(B_m\right)[/itex] then [itex]A(P(B,j))=A\left(P\left(B_m,j\right)\right)[/itex]

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

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

    Unfortunately, the library is closing, so this is fire and forget. I don't have time to proof it.
     
    Last edited by a moderator: Nov 18, 2015
  7. Nov 19, 2015 #6
    I have to admit, I cheated. This gave me the nudge that got me started.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Binomial Coefficient Factorial Derivation
Loading...