Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Pascal's rule
open-in-new
<h2 id="combinatorial-proof">Combinatorial proof</h2> <p><a href="/facts/Blaise_Pascal/Huy5LenL">Pascal's</a> rule has an intuitive combinatorial meaning, that is clearly expressed in this counting proof.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>: 44 </p><p><i>Proof</i>. Recall that ( n k ) {\displaystyle {\tbinom {n}{k}}} equals the number of <a href="/facts/Subset/SJGERmbA">subsets</a> with <i>k</i> elements from a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> with <i>n</i> elements. Suppose one particular element is uniquely labeled <i>X</i> in a set with <i>n</i> elements. </p><p>To construct a subset of <i>k</i> elements containing <i>X</i>, include X and choose <i>k</i> − 1 elements from the remaining <i>n</i> − 1 elements in the set. There are ( n − 1 k − 1 ) {\displaystyle {\tbinom {n-1}{k-1}}} such subsets. </p><p>To construct a subset of <i>k</i> elements <i>not</i> containing <i>X</i>, choose <i>k</i> elements from the remaining <i>n</i> − 1 elements in the set. There are ( n − 1 k ) {\displaystyle {\tbinom {n-1}{k}}} such subsets. </p><p>Every subset of <i>k</i> elements either contains <i>X</i> or not. The total number of subsets with <i>k</i> elements in a set of <i>n</i> elements is the sum of the number of subsets containing <i>X</i> and the number of subsets that do not contain <i>X</i>, ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}} . </p><p>This equals ( n k ) {\displaystyle {\tbinom {n}{k}}} ; therefore, ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}} . </p> <h2 id="algebraic-proof">Algebraic proof</h2> <p>Alternatively, the algebraic derivation of the binomial case follows. ( n − 1 k ) + ( n − 1 k − 1 ) = ( n − 1 ) ! k ! ( n − 1 − k ) ! + ( n − 1 ) ! ( k − 1 ) ! ( n − k ) ! = ( n − 1 ) ! [ n − k k ! ( n − k ) ! + k k ! ( n − k ) ! ] = ( n − 1 ) ! n k ! ( n − k ) ! = n ! k ! ( n − k ) ! = ( n k ) . {\displaystyle {\begin{aligned}{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{aligned}}} </p><p>An alternative algebraic proof using the alternative definition of binomial coefficients: ( n k ) = n ( n − 1 ) ⋯ ( n − k + 1 ) k ! {\displaystyle {\tbinom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k!}}} . Indeed </p><p> ( n − 1 k ) + ( n − 1 k − 1 ) = ( n − 1 ) ⋯ ( ( n − 1 ) − k + 1 ) k ! + ( n − 1 ) ⋯ ( ( n − 1 ) − ( k − 1 ) + 1 ) ( k − 1 ) ! = ( n − 1 ) ⋯ ( n − k ) k ! + ( n − 1 ) ⋯ ( n − k + 1 ) ( k − 1 ) ! = ( n − 1 ) ⋯ ( n − k + 1 ) ( k − 1 ) ! [ n − k k + 1 ] = ( n − 1 ) ⋯ ( n − k + 1 ) ( k − 1 ) ! ⋅ n k = n ( n − 1 ) ⋯ ( n − k + 1 ) k ! = ( n k ) . {\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose k-1}&={\frac {(n-1)\cdots ((n-1)-k+1)}{k!}}+{\frac {(n-1)\cdots ((n-1)-(k-1)+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k)}{k!}}+{\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\left[{\frac {n-k}{k}}+1\right]\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\cdot {\frac {n}{k}}\\&={\frac {n(n-1)\cdots (n-k+1)}{k!}}\\&={\binom {n}{k}}.\end{aligned}}} </p><p>Since ( z k ) = z ( z − 1 ) ⋯ ( z − k + 1 ) k ! {\displaystyle {\tbinom {z}{k}}={\frac {z(z-1)\cdots (z-k+1)}{k!}}} is used as the extended definition of the binomial coefficient when <i>z</i> is a complex number, thus the above alternative algebraic proof shows that Pascal's rule holds more generally when <i>n</i> is replaced by any complex number. </p> <h2 id="generalization">Generalization</h2> <p>Pascal's rule can be generalized to multinomial coefficients.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>: 144 For any <a href="/facts/Integer/PUwwrawx">integer</a> <i>p</i> such that p ≥ 2 {\displaystyle p\geq 2} , k 1 , k 2 , k 3 , … , k p ∈ N + , {\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,} and n = k 1 + k 2 + k 3 + ⋯ + k p ≥ 1 {\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1} , ( n − 1 k 1 − 1 , k 2 , k 3 , … , k p ) + ( n − 1 k 1 , k 2 − 1 , k 3 , … , k p ) + ⋯ + ( n − 1 k 1 , k 2 , k 3 , … , k p − 1 ) = ( n k 1 , k 2 , k 3 , … , k p ) {\displaystyle {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}}} where ( n k 1 , k 2 , k 3 , … , k p ) {\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}} is the coefficient of the x 1 k 1 x 2 k 2 ⋯ x p k p {\displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_{p}}} term in the expansion of ( x 1 + x 2 + ⋯ + x p ) n {\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}} . </p><p>The algebraic derivation for this general case is as follows.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>: 144 Let <i>p</i> be an integer such that p ≥ 2 {\displaystyle p\geq 2} , k 1 , k 2 , k 3 , … , k p ∈ N + , {\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,} and n = k 1 + k 2 + k 3 + ⋯ + k p ≥ 1 {\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1} . Then ( n − 1 k 1 − 1 , k 2 , k 3 , … , k p ) + ( n − 1 k 1 , k 2 − 1 , k 3 , … , k p ) + ⋯ + ( n − 1 k 1 , k 2 , k 3 , … , k p − 1 ) = ( n − 1 ) ! ( k 1 − 1 ) ! k 2 ! k 3 ! ⋯ k p ! + ( n − 1 ) ! k 1 ! ( k 2 − 1 ) ! k 3 ! ⋯ k p ! + ⋯ + ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ ( k p − 1 ) ! = k 1 ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! + k 2 ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! + ⋯ + k p ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = ( k 1 + k 2 + ⋯ + k p ) ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = n ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = n ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = ( n k 1 , k 2 , k 3 , … , k p ) . {\displaystyle {\begin{aligned}&{}\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{aligned}}} </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Pascal%2527s_triangle/tb6BKXbc">Pascal's triangle</a></li> <li><a href="/facts/Hockey-stick_identity/7d9eYNsu">Hockey-stick identity</a></li></ul> <h2 id="bibliography">Bibliography</h2> <ul><li>Merris, Russell. <a href="http://media.wiley.com/product_data/excerpt/6X/04712629/047126296X.pdf"><i>Combinatorics</i></a>. John Wiley & Sons. 2003 <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-471-26296-1</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="https://planetmath.org/CentralBinomialCoefficient">"Central binomial coefficient"</a>. <i><a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a></i>.</li> <li><a href="https://planetmath.org/BinomialCoefficient">"Binomial coefficient"</a>. <i><a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a></i>.</li></ul> <p><i>This article incorporates material from <a href="https://planetmath.org/PascalsTriangle">Pascal's triangle</a> on <a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a>, which is licensed under the Creative Commons Attribution/Share-Alike License.</i> </p><p><i>This article incorporates material from <a href="https://planetmath.org/pascalsruleproof">Pascal's rule proof</a> on <a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a>, which is licensed under the Creative Commons Attribution/Share-Alike License.</i> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Mazur, David R. (2010), Combinatorics / A Guided Tour, Mathematical Association of America, p. 60, ISBN 978-0-88385-762-5 <a href="978-0-88385-762-5" target="_blank">978-0-88385-762-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0 <a href="978-0-13-602040-0" target="_blank">978-0-13-602040-0</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0 <a href="978-0-13-602040-0" target="_blank">978-0-13-602040-0</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0 <a href="978-0-13-602040-0" target="_blank">978-0-13-602040-0</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> </ol>