Pascal's rule

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, Pascal's rule (or Pascal's formula) is a <a href="/facts/Combinatorics/k14xUoKT">combinatorial</a> <a href="/facts/Identity_(mathematics)/LR46j4uR">identity</a> about <a href="/facts/Binomial_coefficient/Tsx7eY5h">binomial coefficients</a>. The binomial coefficients are the numbers that appear in <a href="/facts/Pascal%2527s_triangle/tb6BKXbc">Pascal's triangle</a>. Pascal's rule states that for <a href="/facts/Natural_number/u65og8JE">positive integers</a> 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 <a href="/facts/Polynomial_expansion/oIe5fBKr">expansion</a> 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 <a href="/facts/Recurrence_relation/JolXC71M">recurrence relation</a> that defines the binomial coefficients.
Pascal's rule can also be generalized to apply to <a href="/facts/Multinomial_coefficient/0kyhtHvf">multinomial coefficients</a>.

Pascal's rule open-in-new

Pascal's rule