Permutation and Combination EqualityDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/