Pascal's rule

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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 which is 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 generalized to apply to multinomial coefficients.

Combinatorial proof[edit]

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

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, choose X and 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.[3] 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.[3] 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. ^ Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, p. 44, ISBN 978-0-13-602040-0
  3. ^ a b Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, p. 144, ISBN 978-0-13-602040-0

Sources[edit]

External links[edit]