Jump to content

Pascal's rule

From Wikipedia, the free encyclopedia

In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. It states that for positive natural numbers n and k, where is a binomial coefficient; one interpretation of the coefficient of the xk term in the expansion of (1 + x)n. There is no restriction on the relative sizes of n and k,[1] since, if n < k the value of the binomial coefficient is zero and the identity remains valid.

Pascal's rule can also be viewed as a statement that the formula solves the linear two-dimensional difference equation over the natural numbers. Thus, Pascal's rule is also a statement about a formula for the numbers appearing in Pascal's triangle.

Pascal's rule can also be generalized to apply to multinomial coefficients.

Combinatorial proof

[edit]
Illustrates combinatorial proof:

Pascal's rule has an intuitive combinatorial meaning, that is clearly expressed in this counting proof.[2]: 44 

Proof. Recall that equals the number of subsets with k elements from a set with n elements. Suppose one particular element is uniquely labeled X in a set with n elements.

To construct a subset of k elements containing X, include X and choose k − 1 elements from the remaining n − 1 elements in the set. There are such subsets.

To construct a subset of k elements not containing X, choose k elements from the remaining n − 1 elements in the set. There are such subsets.

Every subset of k elements either contains X or not. The total number of subsets with k elements in a set of n elements is the sum of the number of subsets containing X and the number of subsets that do not contain X, .

This equals ; therefore, .

Algebraic proof

[edit]

Alternatively, the algebraic derivation of the binomial case follows.

Generalization

[edit]

Pascal's rule can be generalized to multinomial coefficients.[2]: 144  For any integer p such that , and , where is the coefficient of the term in the expansion of .

The algebraic derivation for this general case is as follows.[2]: 144  Let p be an integer such that , and . Then

See also

[edit]

References

[edit]
  1. ^ Mazur, David R. (2010), Combinatorics / A Guided Tour, Mathematical Association of America, p. 60, ISBN 978-0-88385-762-5
  2. ^ a b c Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0

Bibliography

[edit]
[edit]

This article incorporates material from Pascal's triangle on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

This article incorporates material from Pascal's rule proof on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.