Pascal's rule




Not to be confused with Pascal's law.

In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. It states that for positive natural numbers n and k,



(n−1k)+(n−1k−1)=(nk){displaystyle {n-1 choose k}+{n-1 choose k-1}={n choose k}}{displaystyle {n-1 choose k}+{n-1 choose k-1}={n choose k}} with 1≤k≤n,{displaystyle 1leq kleq n,}{displaystyle 1leq kleq n,}

where (nk){displaystyle {n choose k}}{n choose k} is the binomial coefficient of the xk term in the expansion of (1 + x)n.


Pascal's rule can also be generalized to apply to multinomial coefficients.




Contents






  • 1 Combinatorial proof


  • 2 Algebraic proof


  • 3 Generalization


  • 4 See also


  • 5 References


  • 6 Sources


  • 7 External links





Combinatorial proof


Pascal's rule has an intuitive combinatorial meaning, that is clearly expressed in this counting proof.[1]


Proof. Recall that (nk){displaystyle {n choose k}}{n choose k} equals the number of subsets with k elements from a 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, choose X and k-1 elements from the remaining n-1 elements in the set. There are (n−1k−1){displaystyle {n-1 choose k-1}}{n-1 choose k-1} such subsets.


To construct a subset of k elements not containing X, choose k elements from the remaining n-1 elements in the set. There are (n−1k){displaystyle {n-1 choose k}}{displaystyle {n-1 choose k}} 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, (n−1k−1)+(n−1k){displaystyle {n-1 choose k-1}+{n-1 choose k}}{displaystyle {n-1 choose k-1}+{n-1 choose k}}.


This equals (nk){displaystyle {n choose k}}{n choose k}; therefore, (nk)=(n−1k−1)+(n−1k){displaystyle {n choose k}={n-1 choose k-1}+{n-1 choose k}}{displaystyle {n choose k}={n-1 choose k-1}+{n-1 choose k}}.



Algebraic proof


Alternatively, the algebraic derivation of the binomial case follows.


(n−1k)+(n−1k−1)=(n−1)!k!(n−1−k)!+(n−1)!(k−1)!(n−k)!=(n−1)![n−kk!(n−k)!+kk!(n−k)!]=(n−1)!nk!(n−k)!=n!k!(n−k)!=(nk).{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}}}{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}}}



Generalization


Pascal's rule can be generalized to multinomial coefficients.[2] For any integer p such that p≥2{displaystyle pgeq 2}pgeq 2, k1,k2,k3,…,kp∈N∗{displaystyle k_{1},k_{2},k_{3},dots ,k_{p}in mathbb {N} ^{*}}{displaystyle k_{1},k_{2},k_{3},dots ,k_{p}in mathbb {N} ^{*}}, and n=k1+k2+k3+⋯+kp≥1{displaystyle n=k_{1}+k_{2}+k_{3}+cdots +k_{p}geq 1}{displaystyle n=k_{1}+k_{2}+k_{3}+cdots +k_{p}geq 1},


(n−1k1−1,k2,k3,…,kp)+(n−1k1,k2−1,k3,…,kp)+⋯+(n−1k1,k2,k3,…,kp−1)=(nk1,k2,k3,…,kp){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}}}{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 (nk1,k2,k3,…,kp){displaystyle {n choose k_{1},k_{2},k_{3},dots ,k_{p}}}{displaystyle {n choose k_{1},k_{2},k_{3},dots ,k_{p}}} is the coefficient of the x1k1x2k2…xpkp{displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}dots x_{p}^{k_{p}}}{displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}dots x_{p}^{k_{p}}} term in the expansion of (x1+x2+⋯+xp)n{displaystyle (x_{1}+x_{2}+dots +x_{p})^{n}}{displaystyle (x_{1}+x_{2}+dots +x_{p})^{n}}.


The algebraic derivation for this general case is as follows.[2] Let p be an integer such that p≥2{displaystyle pgeq 2}pgeq 2, k1,k2,k3,…,kp∈N∗{displaystyle k_{1},k_{2},k_{3},dots ,k_{p}in mathbb {N} ^{*}}{displaystyle k_{1},k_{2},k_{3},dots ,k_{p}in mathbb {N} ^{*}}, and n=k1+k2+k3+⋯+kp≥1{displaystyle n=k_{1}+k_{2}+k_{3}+cdots +k_{p}geq 1}{displaystyle n=k_{1}+k_{2}+k_{3}+cdots +k_{p}geq 1}. 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


References





  1. ^ Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, p. 44, ISBN 978-0-13-602040-0.mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .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 .citation .cs1-lock-limited a,.mw-parser-output .citation .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 .citation .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-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.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}


  2. ^ ab Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, p. 144, ISBN 978-0-13-602040-0




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
    ISBN 978-0-471-26296-1



External links




  • "Central binomial coefficient". PlanetMath.


  • "Binomial coefficient". PlanetMath.


  • "Pascal's triangle". PlanetMath.




-

這個網誌中的熱門文章

12.7 cm/40 Type 89 naval gun

圖片
12.7 cm/40 Type 89 naval gun Type 89 gun mounted on Chitose Type Naval gun anti-aircraft gun Place of origin Japan Service history In service 1932–45 Used by Imperial Japanese Navy Wars World War II Production history Designed 1928–32 Produced 1932–45 No.  built ~1500 Variants Type 88 Specifications Mass 3,100 kilograms (6,834 lb) Barrel length 5,080 millimeters (16 ft 8 in) (bore length) Shell Fixed Shell weight 20.9–23.45 kilograms (46.1–51.7 lb) Caliber 12.7-centimeter (5.0 in) Breech horizontal breech block Elevation -8° to +90° [1] Rate of fire 8-14 rounds per minute Muzzle velocity 720–725 meters per second (2,360–2,380 ft/s) Maximum firing range 9,440 meters (30,970 ft) at 90° (AA ceiling) 14,800 meters (48,600 ft) at 45° The 12.7 cm/40 Type 89 naval gun was a Japanese anti-aircraft (AA) gun introduced before World War II. It was the Imperial Japanese Navy's standard heavy AA
閱讀完整內容

Shark

圖片
For other uses, see Shark (disambiguation). Sharks Temporal range: Ludfordian-Present, 425–0 Ma PreЄ Є O S D C P T J K Pg N [1] Clockwise from top left: spiny dogfish, Japanese sawshark, whale shark, great white shark, horn shark, frilled shark, scalloped hammerhead and Australian angelshark representing the orders Squaliformes, Pristiophoriformes, Orectolobiformes, Lamniformes, Heterodontiformes, Hexanchiformes, Carcharhiniformes and Squatiniformes respectively. Scientific classification Kingdom: Animalia Phylum: Chordata Class: Chondrichthyes Subclass: Elasmobranchii Infraclass: Euselachii Superorder: Selachimorpha Orders Carcharhiniformes Heterodontiformes Hexanchiformes Lamniformes Orectolobiformes Pristiophoriformes Squaliformes Squatiniformes † Cladoselachiformes † Hybodontiformes † Symmoriida † Xenacanthida (Xenacantiformes) † Elegestolepis † = extinct Synonyms Pleurotremata Sharks
閱讀完整內容

Wiciokrzew

圖片
Wiciokrzew, suchodrzew Morfologia (wiciokrzew pospolity) Systematyka [1] Domena eukarionty Królestwo rośliny Klad rośliny naczyniowe Klad rośliny nasienne Klasa okrytonasienne Klad astrowe Rząd szczeciowce Rodzina przewiertniowate Rodzaj wiciokrzew Nazwa systematyczna Lonicera L. Sp. Pl. 173. 1 Mai 1753 Typ nomenklatoryczny Lonicera caprifolium L. [2] Multimedia w Wikimedia Commons Hasło w Wikisłowniku Kwiaty suchodrzewu pospolitego Owoce suchodrzewu pospolitego Kwiaty wiciokrzewu pomorskiego Kwiaty wiciokrzewu przewiercienia Wiciokrzew , suchodrzew ( Lonicera L.) – rodzaj roślin wieloletnich należący do rodziny przewiertniowatych ( Caprifoliaceae ). Rośliny zielne i pnące nazywane są wiciokrzewami, natomiast krzewy i niewielkie drzewa – suchodrzewami. Rodzaj liczy około 180 gatunków szeroko rozprzestrzenionych na całej półkuli północnej [3] [4]
閱讀完整內容