Pascal's rule




Not to be confused with Pascal's law.

In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for any natural number n we have


(n−1k)+(n−1k−1)=(nk)for 1≤k≤n{displaystyle {n-1 choose k}+{n-1 choose k-1}={n choose k}quad {text{for }}1leq kleq n}{n-1 choose k}+{n-1 choose k-1}={n choose k}quad {text{for }}1leq kleq n

where (nk){displaystyle {n choose k}}{n choose k} is a binomial coefficient. This is also commonly written


(nk)+(nk−1)=(n+1k)for 1≤k≤n+1{displaystyle {n choose k}+{n choose k-1}={n+1 choose k}quad {text{for }}1leq kleq n+1}{n choose k}+{n choose k-1}={n+1 choose k}quad {text{for }}1leq kleq n+1



Contents






  • 1 Combinatorial proof


  • 2 Algebraic proof


  • 3 Generalization


  • 4 See also


  • 5 Sources


  • 6 External links





Combinatorial proof


Pascal's rule has an intuitive combinatorial meaning. Recall that (ab){displaystyle {a choose b}}{a choose b} counts in how many ways can we pick a subset with b elements out from a set with a elements. Therefore, the right side of the identity (nk){displaystyle {n choose k}}{n choose k} is counting how many ways can we get a k-subset out from a set with n elements.


Now, suppose you distinguish a particular element 'X' from the set with n elements. Thus, every time you choose k elements to form a subset there are two possibilities: X belongs to the chosen subset or not.


If X is in the subset, you only really need to choose k − 1 more objects (since it is known that X will be in the subset) out from the remaining n − 1 objects. This can be accomplished in (n−1k−1){displaystyle n-1 choose k-1}{n-1 choose k-1} ways.


When X is not in the subset, you need to choose all the k elements in the subset from the n − 1 objects that are not X. This can be done in (n−1k){displaystyle n-1 choose k}{n-1 choose k} ways.


We conclude that the numbers of ways to get a k-subset from the n-set, which we know is (nk){displaystyle {n choose k}}{n choose k}, is also the number
(n−1k−1)+(n−1k).{displaystyle {n-1 choose k-1}+{n-1 choose k}.}{n-1 choose k-1}+{n-1 choose k}.


See also Bijective proof.



Algebraic proof


We need to show


(nk)+(nk−1)=(n+1k).{displaystyle {n choose k}+{n choose k-1}={n+1 choose k}.}{n choose k}+{n choose k-1}={n+1 choose k}.



(nk)+(nk−1)=n!k!(n−k)!+n!(k−1)!(n−k+1)!=n![n−k+1k!(n−k+1)!+kk!(n−k+1)!]=n!(n+1)k!(n−k+1)!=(n+1k){displaystyle {begin{aligned}{n choose k}+{n choose k-1}&={frac {n!}{k!(n-k)!}}+{frac {n!}{(k-1)!(n-k+1)!}}\&=n!left[{frac {n-k+1}{k!(n-k+1)!}}+{frac {k}{k!(n-k+1)!}}right]\&={frac {n!(n+1)}{k!(n-k+1)!}}={binom {n+1}{k}}end{aligned}}}{displaystyle {begin{aligned}{n choose k}+{n choose k-1}&={frac {n!}{k!(n-k)!}}+{frac {n!}{(k-1)!(n-k+1)!}}\&=n!left[{frac {n-k+1}{k!(n-k+1)!}}+{frac {k}{k!(n-k+1)!}}right]\&={frac {n!(n+1)}{k!(n-k+1)!}}={binom {n+1}{k}}end{aligned}}}


Generalization


Let n,k1,k2,k3,…,kp,p∈N∗{displaystyle n,k_{1},k_{2},k_{3},dots ,k_{p},pin mathbb {N} ^{*}}{displaystyle n,k_{1},k_{2},k_{3},dots ,k_{p},pin mathbb {N} ^{*}} and n=k1+k2+k3+⋯+kp{displaystyle n=k_{1}+k_{2}+k_{3}+cdots +k_{p}}{displaystyle n=k_{1}+k_{2}+k_{3}+cdots +k_{p}}. Then


(n−1k1−1,k2,k3,…,kp)+(n−1k1,k2−1,k3,…,kp)+⋯+(n−1k1,k2,k3,…,kp−1)=(n−1)!(k1−1)!k2!k3!⋯kp!+(n−1)!k1!(k2−1)!k3!⋯kp!+⋯+(n−1)!k1!k2!k3!⋯(kp−1)!=k1(n−1)!k1!k2!k3!⋯kp!+k2(n−1)!k1!k2!k3!⋯kp!+⋯+kp(n−1)!k1!k2!k3!⋯kp!=(k1+k2+⋯+kp)(n−1)!k1!k2!k3!⋯kp!=n(n−1)!k1!k2!k3!⋯kp!=n!k1!k2!k3!⋯kp!=(nk1,k2,k3,…,kp).{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}}}{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}}


See also


  • Pascal's triangle


Sources



  • This article incorporates material from Pascal's rule on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

  • This article incorporates material from Pascal's rule proof on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

  • Merris, Russell. Combinatorics. John Wiley & Sons. 2003 .mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
    ISBN 978-0-471-26296-1



External links




  • "Central binomial coefficient". PlanetMath.


  • "Binomial coefficient". PlanetMath.


  • "Pascal's triangle". PlanetMath.




-

Popular posts from this blog

Daylamites

Image
Map showing Daylam in western Tabaristan. The Daylamites or Dailamites (Middle Persian: Daylamīgān ; Persian: دیلمیان ‎ Deylamiyān ) were an Iranian people inhabiting the Daylam—the mountainous regions of northern Iran on the southern shore of the Caspian Sea. [1] They were employed as soldiers from the time of the Sasanian Empire, and long resisted the Muslim conquest of Persia and subsequent Islamization. In the 930s, the Daylamite Buyid dynasty emerged and managed to gain control over much of modern-day Iran, which it held until the coming of the Seljuq Turks in the mid-11th century. Contents 1 Origins, language and equipment 2 History 2.1 Pre-Islamic period 2.1.1 Seleucid and Parthian period 2.1.2 Sasanian period 2.2 Islamic period 2.2.1 Resistance to the Arabs 2.2.2 The Daylamite expansion 3 Culture 3.1 Names 3.2 Religion 3.3 Customs, equipment and appearance 4 References 5 Sources Origins, langu...
Read more

Czechs

Image
Czechs Češi Flag of the Czech Republic Total population c.   10–12 million Regions with significant populations   Czech Republic    6,732,104 [1] [nb 1] – 9 246 784 [2] Significant diasporic populations in:   United States 1,462,000 [3]   Canada 94,805 [4]   Germany 60,000   Israel 50,000   Argentina 45,000   United Kingdom 45,000 [5]   Austria 40,324 [6]   Italy 40,000   France 38,000   Slovakia 30,367 [7]   Australia 21,196 [8]    Switzerland 20,000   Croatia 9,641 (2011)   Chile 8,600   Ukraine 11,000   Sweden 7,175 (2001)   Ireland 5,451 [9]   Spain 5,622 (2006)   Russia 5,000–6,000   Netherlands 3,500   Romania 3,339 (2002)   Poland 3,000   South Africa 2,300   Mexico 2,000   Venezuela 2,000   Serbia 1,824 (2011) [10]   Colombia 1,200   New Zealand 1,083   Kazakhstan 1,000 [11]   Bo...
Read more

Lambaréné

Image
Place in Moyen-Ogooué, Gabon Lambaréné Street in Lambaréné Lambaréné Location in Gabon Coordinates: 0°41′18″S 10°13′55″E  /  0.68833°S 10.23194°E  / -0.68833; 10.23194 Coordinates: 0°41′18″S 10°13′55″E  /  0.68833°S 10.23194°E  / -0.68833; 10.23194 Country   Gabon Province Moyen-Ogooué Population (2013 census)  • Total 38,775 Lambaréné is a town and the capital of Moyen-Ogooué in Gabon. With a population of 38,775 as of 2013, it is located 75 kilometres south of the equator. Lambaréné is based in the Central African Rainforest at the river Ogooué. This river divides the city into 3 districts: Rive Gauche, Ile Lambaréné and Rive Droite. The Albert Schweitzer Hospital and the districts Adouma and Abongo are located on Rive Droite. The districts Atongowanga, Sahoty, Dakar, Grand Village, Château, Lalala and Bordamur build the Ile Lambaréné. The majority of the people in Lambaréné live in the district Isaac located on Rive Gauche. This distr...
Read more