How do i go about proving the following trinomial Revision Property
n choosing k times k choosing r equals n choosing r times n minus r
choosing k minus r

(n)(k) = (n)(n-r)
(k)(r)     (r)(k-r)

The key to proving this property is to know how the binomial
coefficient is calculated. Given n distinct items, the number of ways
to choose m among them is written

    C(n, m)

and properly pronounced "n choose m". The formula to calculate it is

                     n! 
    C(n, m)  =  ----------- 
                (n-m)! * m!

where "!" is used to denote the factorial function, so that, for example,

    n!  =  n * (n-1) * (n-2) * ... * 2 * 1.

An article in Eric Weisstein's Mathworld describes the binomial
coefficient in greater detail.

    http://mathworld.wolfram.com/BinomialCoefficient.html


I shall begin by rewriting your equation using the standard notation.

    C(n, k) * C(k, r)  =  C(n, r) * C(n-r, k-r)

This says that the product of n choose k with k choose r is equal to
the product of n choose r with n-r choose k-r. We expand both sides of
the equation by applying the formula for the binomial coefficient.

         n!            k!              n!                (n-r)!
    ----------- * -----------  =  ----------- * -----------------------
    (n-k)! * k!   (k-r)! * r!     (n-r)! * r!   (n-r - (k-r))! * (k-r)!

Notice that both sides of the equation have common factors in the
numerator and denominator. We divide both sides by n!, and multiply
both sides by r! and (k-r)!.

         1         k!        1          (n-r)!
    ----------- * ----  =  ------ * --------------
    (n-k)! * k!    1       (n-r)!   (n-r - (k-r))!

In the denominator on the right-hand side, we see that

    (n-r - (k-r))!  =  (n - r - k + r)
                    =  (n - k)

so we can simplify the equation to

         1         k!        1      (n-r)!
    ----------- * ----  =  ------ * ------
    (n-k)! * k!    1       (n-r)!   (n-k)!

and, after multiplying both sides by (n-k)!, further to

     1      k!        1      (n-r)!
    ---- * ----  =  ------ * ------.
     k!     1       (n-r)!     1

But this is just

     k!      (n-r)!
    ----  =  ------
     k!      (n-r)!

or

    1 = 1

which holds trivially. Thus, we have shown that the equation

    C(n, k) * C(k, r)  =  C(n, r) * C(n-r, k-r)

is true.


If you find my answer incomplete or inaccurate in any way, please let
me know so that I have a chance to meet your needs before you assign a
rating.

leapinglizard

---

Clarification of Answer by leapinglizard-ga on 09 Dec 2003 08:06 PST

My proof contains a typographical error that does not detract from its correctness.

It currently reads:

> In the denominator on the right-hand side, we see that
>
>     (n-r - (k-r))!  =  (n - r - k + r)

It should read:

> In the denominator on the right-hand side, we see that
>
>     (n-r - (k-r))  =  (n - r - k + r)

In effect, there's a superfluous exclamation mark.

leapinglizard

perfect answer

I'm surprised no one considered a combinatorial approach here. This is
a correct way to prove it algebraically, but some thought will show
why this is actually true in real life.

Suppose I have n senators, and I choose k to be on a committee. Then
in the committee, I choose r to be co-heads. We have (n choose k) * (k
choose r) ways to do this. This is identical to situation two: suppose
I have n senators, and I choose r to be co-heads of a committee. Then,
out of the remaining n - r senators, I choose (k - r) to form the rest
of the non-co-head committee. The number of possibilities in this
situation is (n choose r) * (n-r choose k-r). Thus, (n choose k) * (k
choose r) = (n choose r) * (n-r choose k-r).

Just a thought,

Entropix