Паскалово правило

Паскалово правило — комбинаторно равенство за биномни коефициенти. Според правилото, за секој природен број n важи:

${n-1 \choose k}+{n-1 \choose k-1}={n \choose k}\quad {\text{for }}1\leq k\leq n$

каде ${n \choose k}$ е биномен коефициент. Ова обично се запишува и како:

${n \choose k}+{n \choose k-1}={n+1 \choose k}\quad {\text{for }}1\leq k\leq n+1$

Правилото е именувано по францускиот математичар Блез Паскал.

Комбинаторен доказ

Паскаловото правило има интуитивно комбинаторно значење. Ако се потсетиме дека ${a \choose b}$ означува на колку многу начини може да се избере подмножество со b елементи од множество со a елементи. Поради тоа, десната страна на равенството ${n \choose k}$ претставува пребројување за тоа на колку начини може да се избере подмножество со k елементи од множество со n елементи.

Претпоставуваме дека во множеството со n елементи се разликува некој член x. На тој начин, секој пат кога се избира подмножество со k елементи, постојат две можности: x се наоѓа во подмножеството или не. Ако x се наоѓа во подмножеството, потребно е да се изберат уште само k - 1 елементи (затоа што е познато дека x ќе биде во подмножеството) од преостанатите n - 1 елементи. Ова може да биде направено на $n-1 \choose k-1$. Ако x не се наоѓа во подмножеството, потребно е да се изберат сите k елементи од n - 1 елементи што се разликуваат од x. Ова може да биде направено на $n-1 \choose k$ начини. Оттука може да се заклучи дека бројот на начини за да избере подмножество со k елементи од множество со n елементи, што изнесува ${n \choose k}$, е исто така еднакво на ${n-1 \choose k-1}+{n-1 \choose k}.$

Алгебарски доказ

Во алгебарскиот доказ е потребно да се докаже следното:

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

Со разложување на десната страна од равенството се добива:

${\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+1-k}{k!(n+1-k)!}}+{\frac {k}{k!(n+1-k)!}}\right]\\&={\frac {n!(n+1)}{k!(n+1-k)!}}={\binom {n+1}{k}}\end{aligned}}$

Воопштување

Нека $n,k_{1},k_{2},k_{3},\dots ,k_{p},p\in \mathbb {N} ^{*}\,\!$ и $n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\,\!$. Тогаш, следува дека:

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

Поврзано

• Паскалов триаголник

Користена литература

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

Надворешни врски

• Central binomial coefficient - PlanetMath (англиски)
• Binomial coefficient - PlanetMath (англиски)
• Pascal's triangle - PlanetMath (англиски)