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
Math Forum Home || Math Library || Quick Reference || Math Forum Search