View source for Pascal's rule

{{Short description|Combinatorial identity about binomial coefficients}}
{{distinguish|Pascal's law}}
In [[mathematics]], '''Pascal's rule''' (or '''Pascal's formula''') is a [[combinatorics|combinatorial]] [[identity (mathematics)|identity]] about [[binomial coefficient]]s. It states that for positive [[natural number|natural numbers]] ''n'' and ''k'', 
<math display="block">{n-1\choose k} + {n-1\choose k-1} = {n\choose k},</math> 
where <math>\tbinom{n}{k}</math> is a binomial coefficient; one interpretation of  the coefficient of the {{math|''x''<sup>''k''</sup>}} term in the [[polynomial expansion|expansion]] of {{math|(1 + ''x'')<sup>''n''</sup>}}. There is no restriction on the relative sizes of {{mvar|n}} and {{mvar|k}},<ref>{{citation| first=David R.|last=Mazur| title=Combinatorics / A Guided Tour| year=2010| publisher=Mathematical Association of America| page=60| isbn=978-0-88385-762-5}}</ref> since, if {{math|''n'' < ''k''}} 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
<math display="block">\frac{(x+y)!}{x!y!} = {x+y \choose x} = {x+y \choose y} </math>
solves the linear two-dimensional difference equation
<math display="block"> N_{x,y} = N_{x-1,y} + N_{x,y-1}, \quad N_{0,y} = N_{x,0} = 1 </math>
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 coefficient]]s.

==Combinatorial proof==
[[File:Pascal's rule 4c1 plus 4c2 equals 5c2.svg|thumb|Illustrates combinatorial proof: <math>\binom 4 1+\binom 4 2=\binom 5 2.</math>]]
[[Blaise Pascal|Pascal's]] rule has an intuitive combinatorial meaning, that is clearly expressed in this counting proof.<ref name="Brualdi"/>{{rp|p=44}}

''Proof''. Recall that <math>\tbinom{n}{k}</math> equals the number of [[subset]]s with ''k'' elements from a [[Set (mathematics)|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''&thinsp;−&thinsp;1 elements from the remaining ''n''&thinsp;−&thinsp;1 elements in the set. There are <math>\tbinom{n-1}{k-1}</math> such subsets.

To construct a subset of ''k'' elements ''not'' containing ''X'', choose ''k'' elements from the remaining ''n''&thinsp;−&thinsp;1 elements in the set. There are <math>\tbinom{n-1}{k}</math> 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'', <math>\tbinom{n-1}{k-1} + \tbinom{n-1}{k}</math>.

This equals <math>\tbinom{n}{k}</math>; therefore, <math>\tbinom{n}{k} = \tbinom{n-1}{k-1} + \tbinom{n-1}{k}</math>.

==Algebraic proof==

Alternatively, the algebraic derivation of the binomial case follows.
<math display="block">\begin{align}
{ n-1 \choose k } + { n-1 \choose k-1} & = \frac{(n-1)!}{k! (n - 1 - k)!} + \frac{(n-1)!}{(k - 1)!(n - k)!} \\
& = (n-1)! \left[ \frac{n - k}{k!(n - k)!} + \frac{k}{k!(n - k)!}\right] \\
& = (n-1)! \frac{n}{k!(n - k)!} \\
& = \frac{n!}{k!(n - k)!} \\
& = \binom{n}{k}.
\end{align}</math>

==Generalization==
Pascal's rule can be generalized to multinomial coefficients.<ref name=Brualdi>{{citation|first=Richard A.|last=Brualdi| title=Introductory Combinatorics| edition=5th| year=2010| publisher=Prentice-Hall| isbn=978-0-13-602040-0}}</ref>{{rp|p=144}} For any [[integer]] ''p'' such that <math>p \ge 2</math>, <math>k_1, k_2, k_3, \dots, k_p \in \mathbb{N}^{+}\!,</math> and <math>n = k_1 + k_2 + k_3 + \cdots + k_p \ge 1</math>,
<math display="block">{n-1\choose k_1-1,k_2,k_3, \dots, k_p}+{n-1 \choose k_1,k_2-1,k_3,\dots, k_p}+\cdots+{n-1\choose k_1,k_2,k_3,\dots,k_p-1} = {n\choose k_1, k_2, k_3, \dots, k_p}</math>
where <math>{n\choose k_1, k_2, k_3, \dots , k_p}</math> is the coefficient of the <math>x_1^{k_1}x_2^{k_2}\cdots x_p^{k_p}</math> term in the expansion of <math>(x_1 + x_2 + \dots + x_p)^{n}</math>.

The algebraic derivation for this general case is as follows.<ref name=Brualdi />{{rp|p=144}} Let ''p'' be an integer such that <math>p \ge 2</math>, <math>k_1, k_2, k_3, \dots, k_p \in \mathbb{N}^{+}\!,</math> and <math>n = k_1 + k_2 + k_3 + \cdots + k_p \ge 1</math>. Then
<math display="block">
\begin{align}
& {} \quad {n-1 \choose k_1-1,k_2,k_3, \dots, k_p}+{n-1 \choose k_1,k_2-1,k_3,\dots, k_p} + \cdots + {n-1 \choose k_1,k_2,k_3,\dots,k_p-1} \\
& = \frac{(n-1)!}{(k_1-1)!k_2!k_3! \cdots k_p!} + \frac{(n-1)!}{k_1!(k_2-1)!k_3!\cdots k_p!} + \cdots + \frac{(n-1)!}{k_1!k_2!k_3! \cdots (k_p-1)!} \\
& = \frac{k_1(n-1)!}{k_1!k_2!k_3! \cdots k_p!} + \frac{k_2(n-1)!}{k_1!k_2!k_3! \cdots k_p!} + \cdots + \frac{k_p(n-1)!}{k_1!k_2!k_3! \cdots k_p!} = \frac{(k_1+k_2+\cdots+k_p) (n-1)!}{k_1!k_2!k_3!\cdots k_p!}  \\
& = \frac{n(n-1)!}{k_1!k_2!k_3! \cdots k_p!} = \frac{n!}{k_1!k_2!k_3! \cdots k_p!}
= {n \choose k_1, k_2, k_3, \dots, k_p}.
\end{align}
</math>

==See also==
* [[Pascal's triangle]]
* [[Hockey-stick identity]]

==References==
{{reflist}}

==Bibliography==

*Merris, Russell. [http://media.wiley.com/product_data/excerpt/6X/04712629/047126296X.pdf''Combinatorics'']. John Wiley & Sons. 2003 {{ISBN|978-0-471-26296-1}}

==External links==
* {{planetmath reference|urlname=CentralBinomialCoefficient|title=Central binomial coefficient}}
* {{planetmath reference|urlname=BinomialCoefficient|title=Binomial coefficient}}

{{PlanetMath attribution|title=Pascal's triangle|urlname=PascalsTriangle}}

{{PlanetMath attribution|title= Pascal's rule proof|urlname=pascalsruleproof}}

{{DEFAULTSORT:Pascal's Rule}}
[[Category:Combinatorics]]
[[Category:Algebraic identities]]
[[Category:Articles containing proofs]]