Pascals Regel - Pascal's rule

In der Mathematik ist die Pascalsche Regel (oder die Pascalsche Formel ) eine kombinatorische Identität über Binomialkoeffizienten . Darin heißt es , dass für positive natürliche Zahlen n und k ,

${\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},}$

wobei ein Binomialkoeffizient ist; eine Interpretation davon ist der Koeffizient des x ^k- Terms bei der Entwicklung von (1 + x ) ⁿ . Es gibt keine Einschränkung bezüglich der relativen Größen von n und k , da bei n < k der Wert des Binomialkoeffizienten Null ist und die Identität gültig bleibt. ${\displaystyle {\tbinom {n}{k}}}$

Die Pascalsche Regel kann auch als Aussage angesehen werden, dass die Formel

${\displaystyle {\frac {(x+y)!}{x!y!}}={x+y \choose x}={x+y \choose y}}$

löst die lineare zweidimensionale Differenzengleichung

${\displaystyle N_{x,y}=N_{x-1,y}+N_{x,y-1},\quad N_{0,y}=N_{x,0}=1}$

über den natürlichen Zahlen. Somit ist die Pascalsche Regel auch eine Aussage über eine Formel für die im Pascalschen Dreieck vorkommenden Zahlen .

Die Pascalsche Regel kann auch auf multinomiale Koeffizienten verallgemeinert werden .

Kombinatorischer Beweis

Die Pascalsche Regel hat eine intuitive kombinatorische Bedeutung, die in diesem Zählbeweis deutlich zum Ausdruck kommt.

Beweis . Denken Sie daran, dass dies der Anzahl der Teilmengen mit k Elementen aus einer Menge mit n Elementen entspricht. Angenommen, ein bestimmtes Element ist in einer Menge mit n Elementen eindeutig mit X gekennzeichnet . ${\displaystyle {\tbinom {n}{k}}}$

Um eine Teilmenge von k Elementen zu konstruieren, die X enthält , schließen Sie X ein und wählen Sie k  − 1 Elemente aus den verbleibenden n  − 1 Elementen in der Menge. Es gibt solche Teilmengen. ${\displaystyle {\tbinom {n-1}{k-1}}}$

Um eine Teilmenge von konstruieren k Elementen nicht enthalten , X , wählte k Elemente von dem verbleibenden n  - 1 Elemente in dem Satz. Es gibt solche Teilmengen. ${\displaystyle {\tbinom {n-1}{k}}}$

Jede Teilmenge von k Elementen enthält entweder X oder nicht. Die Gesamtzahl der Teilmengen mit k Elementen in einer Menge von n Elementen ist die Summe der Anzahl der Teilmengen, die X enthalten, und der Anzahl der Teilmengen, die X nicht enthalten , . ${\displaystyle {\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}$

Dies entspricht ; daher, . ${\displaystyle {\tbinom {n}{k}}}$${\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}$

Algebraischer Beweis

Alternativ folgt die algebraische Herleitung des Binomialfalls.

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

Verallgemeinerung

Die Pascalsche Regel kann auf multinomiale Koeffizienten verallgemeinert werden. Für jede ganze Zahl p , so dass , und , ${\displaystyle p\geq 2}$${\displaystyle k_{1},k_{2},k_{3},\dots,k_{p}\in\mathbb{N}^{+}\!,}$${\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}$

${\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 \wähle k_{1},k_{2},k_{3},\dots ,k_{p}-1 }={n \wähle k_{1},k_{2},k_{3},\dots,k_{p}}}$

wo ist der Koeffizient des Termes bei der Entwicklung von . ${\displaystyle {n \choose k_{1},k_{2},k_{3},\dots,k_{p}}}$${\displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}\dots x_{p}^{k_{p}}}$${\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}}$

Die algebraische Herleitung für diesen allgemeinen Fall ist wie folgt. Sei p eine ganze Zahl mit , und . Dann ${\displaystyle p\geq 2}$${\displaystyle k_{1},k_{2},k_{3},\dots,k_{p}\in\mathbb{N}^{+}\!,}$${\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}$

${\displaystyle {\begin{ausgerichtet}&{}\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}}}$

Siehe auch

• Pascals Dreieck

Verweise

Literaturverzeichnis

• Merris, Russell. Kombinatorik . John Wiley & Söhne. 2003 ISBN  978-0-471-26296-1

Externe Links

• "Zentraler Binomialkoeffizient" . PlanetMath .
• "Binomialkoeffizient" . PlanetMath .

Dieser Artikel enthält Material aus Pascals Dreieck auf PlanetMath , das unter der Creative Commons-Lizenz Namensnennung/Weitergabe unter gleichen Bedingungen lizenziert ist .

Dieser Artikel enthält Material aus Pascals Regelbeweis auf PlanetMath , das unter der Creative Commons-Lizenz Namensnennung/Weitergabe unter gleichen Bedingungen lizenziert ist .