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,
Pascal's rule can also be viewed as a statement that the formula
Pascal's rule can also be generalized to apply to multinomial coefficients.
Combinatorial proof[edit]
![](https://upload.wikimedia.org/wikipedia/commons/thumb/7/7c/Pascal%27s_rule_4c1_plus_4c2_equals_5c2.svg/220px-Pascal%27s_rule_4c1_plus_4c2_equals_5c2.svg.png)
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 ,
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]
Bibliography[edit]
- Merris, Russell. Combinatorics. John Wiley & Sons. 2003 ISBN 978-0-471-26296-1
External links[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.