Pascal's rule

In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. The binomial coefficients are the numbers that appear in Pascal's triangle. Pascal's rule states that for positive integers n and k, ( n − 1 k ) + ( n − 1 k − 1 ) = ( n k ) , {\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},} where ( n k ) {\displaystyle {\tbinom {n}{k}}} is the binomial coefficient, namely 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; in particular, the above identity remains valid when n < k since ( n k ) = 0 {\displaystyle {\tbinom {n}{k}}=0} whenever n < k. Together with the boundary conditions ( n 0 ) = ( n n ) = 1 {\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1} for all nonnegative integers n, Pascal's rule determines that ( n k ) = n ! k ! ( n − k ) ! , {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},} for all integers 0 ≤ k ≤ n. In this sense, Pascal's rule is the recurrence relation that defines the binomial coefficients. Pascal's rule can also be generalized to apply to multinomial coefficients.