Difference between revisions of "Pascal's Identity"

Revision as of 12:53, 22 December 2007

Pascal's Identity is a common and useful theorem in the realm of combinatorics dealing with combinations (also known as binomial coefficients), and is often used to reduce large, complicated combinations.

Pascal's identity is also known as Pascal's rule, Pascal's formula, and occasionally Pascal's theorem.

Theorem

Pascal's identity states that

${n \choose k}={n-1\choose k-1}+{n-1\choose k}$

for $\{ k,n \in \bbfont{N} | k<n \}$ (Error compiling LaTeX. Unknown error_msg).

This can also be read as that the number of ways to choose $k$ things from $n$ things is equal to the number of ways to choose $k-1$ things from $n-1$ things added to the number of ways to choose $k$ things from $n-1$ things.

Technically, combinations can also be applied to non-integer values of $k$ , in which case the identity still holds.

Proof

We have $\{ k,n \in \bbfont{N} | k<n \}$ (Error compiling LaTeX. Unknown error_msg):

$\binom{n-1}{k-1}+\binom{n-1}{k}=\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}$

$=(n-1)!\left[\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}$ (Error compiling LaTeX. Unknown error_msg)

$=(n-1)!\frac{n}{k!(n-k)!}$

$=\frac{n!}{k!(n-k)!}$

$=\binom{n}{k}$

∎

Alternate Proof

Here, we prove this using committee forming.

Consider picking one fixed object out of $n$ objects. Then, we can choose $k$ objects including that one in $\binom{n-1}{k-1}$ ways.

Because our final group of objects either contains the specified one or doesn't, we can choose the group in $\binom{n-1}{k-1}+\binom{n-1}{k}$ ways.

But we already know they can be picked in $\binom{n}{k}$ ways, so

${n \choose k}={n-1\choose k-1}+{n-1\choose k}$

∎

History

Pascal's identity was probably first derived by Blaise Pascal, a 19th century French mathematician, whom the theorem is named after.

Pascal also did extensive other work on combinatorics, including work on Pascal's triangle, which bears his name. He discovered many patterns in this triangle, and it can be used to prove this identity. The method of proof using that is called block walking.

External Links

Revision as of 12:53, 22 December 2007 (view source) Temperal (talk \| contribs) m (Pascal's identity moved to Pascal's Identity over redirect) ← Older edit		Revision as of 12:53, 22 December 2007 (view source) Temperal (talk \| contribs) (caps) Newer edit →
Line 1:		Line 1:
−	'''Pascal's ~~identity~~''' is a common and useful theorem in the realm of [[combinatorics]] dealing with [[combinations]] (also known as binomial coefficients), and is often used to reduce large, complicated [[combinations]].	+	'''Pascal's Identity''' is a common and useful theorem in the realm of [[combinatorics]] dealing with [[combinations]] (also known as binomial coefficients), and is often used to reduce large, complicated [[combinations]].

	Pascal's identity is also known as Pascal's rule, Pascal's formula, and occasionally Pascal's theorem.		Pascal's identity is also known as Pascal's rule, Pascal's formula, and occasionally Pascal's theorem.

Page

Toolbox

Search