Pascals regel

Ej att förväxla med Pascals lag .

I matematik är Pascals regel (eller Pascals formel ) en kombinatorisk identitet om binomialkoefficienter . Det står att för positiva naturliga tal n och k ,

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

där ${\tbinom {n}{k}}$ är en binomial koefficient; en tolkning av koefficienten för x ^k termen i expansionen av (1 + x ) ⁿ . Det finns ingen begränsning på de relativa storlekarna av n och k , eftersom, om n < k , värdet på den binomiala koefficienten är noll och identiteten förblir giltig.

Pascals regel kan också ses som ett påstående att formeln

$${\frac {(x+y)!}{x!y!}}={x+y \choose x}={x+y \ välj y}$$

löser den linjära tvådimensionella skillnadsekvationen

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

över de naturliga talen. Således är Pascals regel också ett påstående om en formel för talen som förekommer i Pascals triangel .

Pascals regel kan också generaliseras till att gälla multinomialkoefficienter .

Kombinatoriskt bevis

Illustrerar kombinatoriskt bevis: ${\binom {4}{1}}+{\binom {4}{2}}={\binom {5}{2}}.$

Pascals regel har en intuitiv kombinatorisk betydelse, som tydligt uttrycks i detta räknebevis.

Bevis . Kom ihåg att ${\tbinom {n}{k}}$ är lika med antalet delmängder med k element från en mängd med n element. Antag att ett särskilt element är unikt märkt X i en uppsättning med n element.

För att konstruera en delmängd av k element som innehåller X , inkludera X och välj k − 1 element från de återstående n − 1 elementen i mängden. Det finns ${\tbinom {n-1}{k-1}}$ sådana delmängder.

För att konstruera en delmängd av k element som inte innehåller X , välj k element från de återstående n − 1 elementen i mängden. Det finns ${\tbinom {n-1}{k}}$ sådana delmängder.

Varje delmängd av k element innehåller antingen X eller inte. Det totala antalet delmängder med k element i en uppsättning av n element är summan av antalet delmängder som innehåller X och antalet delmängder som inte innehåller X , ${\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}$ .

Detta är lika med ${\tbinom {n}{k}}$ ; därför, ${\tbinom {n}{k}}={\tbinom {n-1}{k-1}} +{\tbinom {n-1}{k}}$ .

Algebraiskt bevis

Alternativt följer den algebraiska härledningen av binomialfallet.

$${\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}}$$

Generalisering

Pascals regel kan generaliseras till multinomialkoefficienter. För vilket heltal p som helst så att $p\geq 2$ , $k_{1},k_{2},k_{ 3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,$ och $n=k_{ 1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1$ ,

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

där ${n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}$ är koefficient för $x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_ {p}}$ term i expansionen av $(x_{1}+x_{2}+\dots +x_{p})^{n}$ .

Den algebraiska härledningen för detta allmänna fall är som följer. Låt p vara ett heltal så att $p\geq 2$ , $k_{1},k_{2},k_ {3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,$ och $n=k_ {1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1$ . Sedan

$${\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}}$$

Se även

• Pascals triangel
• Hockeystick-identitet

Bibliografi

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

externa länkar

• "Central binomial koefficient" . PlanetMath .
• "Binomial koefficient" . PlanetMath .

Den här artikeln innehåller material från Pascals triangel på PlanetMath , som är licensierad under Creative Commons Attribution/Dela Lika-licensen .

Den här artikeln innehåller material från Pascals regelbevis på PlanetMath , som är licensierad under Creative Commons Attribution/Dela Lika-licensen .