Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Permutation and Combination Equality


Date: 07/18/99 at 02:30:10
From: Carlos H. Griese Neto
Subject: Proof of a Permutation and Combination Equality

Prove that

(nC0)^2 + (nC1)^2 + (nC2)^2 + ... + (nCn)^2 = (2nCn)

where nCi = n!/((n-i)!*i!)


Date: 07/18/99 at 08:43:42
From: Doctor Floor
Subject: Re: Proof of a Permutation and Combination Equality

For your problem, we will consider a rhombus from Pascal's triangle:

                1
              1   1
          ...       ...
      ...              ...
C(n, 0)  C(n, 1) ... C(n, n - 1) C(n, n)
      ...              ...
          ...        ...
       C(2n - 1,  n - 1)  C(2n - 1,  n)
              C(2n, n)

We can consider C(2n, n) as a combination of values from the nth row 
in Pascal's triangle. Each entry in the nth row has to be counted for 
the number of routes that there are from that entry to C(2n, n). For 
instance, C(n, 0) has to be counted once, because there is only one 
route from C(n, 0) to C(2n, n) in Pascal's triangle. And C(n, 1) has 
to be counted n times, because there are n routes from C(n, 1) to 
C(2n, n). 

In general, we can see, from the symmetry of the rhombus we have made, 
that the number of routes from C(n, m) to C(2n, n), for any m, is the 
same as the number of routes from C(0, 0) (the top) to C(n, m). But 
the number of routes from C(0, 0) to C(n, m) is equal to C(n, m). So, 
C(n, m) has to be counted C(n, m) times.

And we find,

 C(2n, n) = C(n, 0)^2 + C(n, 1)^2 + ... + C(n, n)^2, 

as desired.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Calculus
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/