Pascal's rule
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 formula_2 is a binomial coefficient; one interpretation of which is the coefficient of the term in the expansion of . There is no restriction on the relative sizes of and , since, if 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. Pascal's rule has an intuitive combinatorial meaning, that is clearly expressed in this counting proof. "Proof". Recall that formula_2 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 formula_6 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 formula_7 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", formula_8. This equals formula_2; therefore, formula_10. Algebraic proof. Alternatively, the algebraic derivation of the binomial case follows . formula_11 Generalization. Pascal's rule can be generalized to multinomial coefficients. For any integer "p" such that formula_12, formula_13 and formula_14, where formula_16 is the coefficient of the formula_17 term in the expansion of formula_18. The algebraic derivation for this general case is as follows. Let "p" be an integer such that formula_12, formula_13 and formula_14. Then