Pascal's rule

Pascal's rule

In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for any natural number "n" we have:{n-1choose k} + {n-1choose k-1} = {nchoose k} where 1 leq k < n and {nchoose k} is a binomial coefficient.

Combinatorial proof

Pascal's rule has an intuitive combinatorial meaning. Recall that {achoose b} counts in how many ways can we pick a subset with "b" elements out from a set with "a" elements. Therefore, the right side of the identity {nchoose k} is counting how many ways can we get a "k"-subset out from a set with "n" elements.

Now, suppose you distinguish a particular element 'X' from the set with "n" elements. Thus, every time you choose "k" elements to form a subset there are two possibilities: "X" belongs to the chosen subset or not.

If "X" is in the subset, you only really need to choose "k" − 1 more objects (since it is known that "X" will be in the subset) out from the remaining "n" − 1 objects. This can be accomplished in n-1choose k-1 ways.

When "X" is not in the subset, you need to choose all the "k" elements in the subset from the "n" − 1 objects that are not "X". This can be done in n-1choose k ways.

We conclude that the numbers of ways to get a "k"-subset from the "n"-set, which we know is {nchoose k}, is also the number{n-1choose k-1} + {n-1choose k}.

See also Bijective proof.

Algebraic proof

We need to show: { n choose k } + { n choose k-1 } = { n+1 choose k }.

Let us begin by writing the left-hand side as

: frac{n!}{k!(n-k)!} + frac{n!}{(k-1)!(n-(k-1))!}.

Getting a common denominator and simplifying, we have

:egin{align}& {} qquad frac{n!}{k!(n-k)!} + frac{n!}{(k-1)!(n-k+1)!} \& = frac{(n-k+1)n!}{(n-k+1)k!(n-k)!}+frac{kn!}{k(k-1)!(n-k+1)!} \& = frac{(n-k+1)n!+kn!}{k!(n-k+1)!} \& = frac{(n+1)n!}{k!((n+1)-k)!} \& = frac{(n+1)!}{k!((n+1)-k)!} \& = { n+1 choose k }.end{align}

Generalization

Let n, k_1, k_2, k_3,dots ,k_p, p in mathbb{N}^* ,! and n=k_1+k_2+k_3+ cdots +k_p ,!. Then

: egin{align}& {} quad {n-1choose k_1-1,k_2,k_3, dots, k_p}+{n-1choose k_1,k_2-1,k_3,dots, k_p}+cdots+{n-1choose k_1,k_2,k_3,dots,k_p-1} \& = frac{(n-1)!}{(k_1-1)!k_2!k_3! cdots k_p!} + frac{(n-1)!}{k_1!(k_2-1)!k_3!cdots k_p!} + cdots + frac{(n-1)!}{k_1!k_2!k_3! cdots (k_p-1)!} \& = frac{k_1(n-1)!}{k_1!k_2!k_3! cdots k_p!} + frac{k_2(n-1)!}{k_1!k_2!k_3! cdots k_p!} + cdots + frac{k_p(n-1)!}{k_1!k_2!k_3! cdots k_p!} = frac{(k_1+k_2+cdots+k_p) (n-1)!}{k_1!k_2!k_3!cdots k_p!} \& = frac{n(n-1)!}{k_1!k_2!k_3! cdots k_p!} = frac{n!}{k_1!k_2!k_3! cdots k_p!}= {nchoose k_1, k_2, k_3, dots , k_p}.end{align}

ee also

* Pascal's triangle

ources

*planetmath|id=246|title=Pascal's rule
*planetmath|id=259|title= Pascal's rule proof
*Merris, Russell. [http://media.wiley.com/product_data/excerpt/6X/04712629/047126296X.pdf"Combinatorics"] . John Wiley & Sons. 2003 ISBN 978-0-471-26296-1

External links

*
*
*


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Pascal's triangle — The first six rows of Pascal s triangle In mathematics, Pascal s triangle is a triangular array of the binomial coefficients in a triangle. It is named after the French mathematician, Blaise Pascal. It is known as Pascal s triangle in much of the …   Wikipedia

  • Pascal (programming language) — Pascal Paradigm(s) imperative, structured Appeared in 1970 Designed by Niklaus Wirth Typing discipline static, strong, safe …   Wikipedia

  • Pascal Salin — (* 16. Mai 1939 in Paris) ist ein französischer Ökonom der Wiener Schule und ehemaliger Universitätsprofessor an der Universität Paris Dauphine. Er ist ehemaliger Präsident der Mont Pelerin Society 1994−1996). Weiterhin ist er adjunct scholar am… …   Deutsch Wikipedia

  • Pascal Brutal — est une série de bande dessinée créée par Riad Sattouf et parue dans le magazine Fluide glacial, puis éditée en trois albums. Cette série porte le nom de son héros, Pascal Brutal, présenté comme « particulièrement viril »[1], dont on… …   Wikipédia en Français

  • Pascal (unit) — pascal A pressure gauge reading in psi (red scale) and kPa (black scale) Unit information Unit system: SI derived unit Unit o …   Wikipedia

  • Comparison of Object Pascal and C — Programming language comparisons General comparison Basic syntax Basic instructions Arrays Associative arrays String operations …   Wikipedia

  • Comparison of Pascal and C — Programming language comparisons General comparison Basic syntax Basic instructions Arrays Associative arrays String operations …   Wikipedia

  • Simpson's rule — can be derived by approximating the integrand f (x) (in blue) by the quadratic interpolant P (x) (in red). In numerical analysis, Simpson s rule is a method for numerical integration, the numerical approximation of definite integrals.… …   Wikipedia

  • Prosper Louis Pascal Gueranger —     Prosper Louis Pascal Guéranger     † Catholic Encyclopedia ► Prosper Louis Pascal Guéranger     Benedictine and polygraph; b. 4 April, 1805, at Sablé sur Sarthe; d. at Solesmes, 30 January, 1875.     Ordained a priest 7 October, 1827, he was… …   Catholic encyclopedia

  • Divisibility rule — A divisibility rule is a shorthand way of discovering whether a given number is divisible by a fixed divisor without performing the division, usually by examining its digits. Although there are divisibility tests for numbers in any radix, and… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”