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

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

(\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) = (\binom{n}{k}) for 1 \leq k \leq n

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

(\binom{n}{k}) + (\binom{n}{k - 1}) = (\binom{n + 1}{k}) for 1 \leq k \leq n + 1

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

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

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

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

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

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

(\binom{n}{k}) + (\binom{n}{k - 1}) = (\binom{n + 1}{k}) .

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

\begin{matrix} (\binom{n}{k}) + (\binom{n}{k - 1}) & = \frac{n!}{k! (n - k)!} + \frac{n!}{(k - 1)! (n - k + 1)!} \\ = n! [\frac{n + 1 - k}{k! (n + 1 - k)!} + \frac{k}{k! (n + 1 - k)!}] \\ = \frac{n! (n + 1)}{k! (n + 1 - k)!} = (\binom{n + 1}{k}) \end{matrix}

Воопштување

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

\begin{matrix} (\binom{n - 1}{k_{1} - 1, k_{2}, k_{3}, \dots, k_{p}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, k_{3}, \dots, k_{p}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, k_{3}, \dots, k_{p} - 1}) \\ = \frac{(n - 1)!}{(k_{1} - 1)! k_{2}! k_{3}! \dots k_{p}!} + \frac{(n - 1)!}{k_{1}! (k_{2} - 1)! k_{3}! \dots k_{p}!} + \dots + \frac{(n - 1)!}{k_{1}! k_{2}! k_{3}! \dots (k_{p} - 1)!} \\ = \frac{k_{1} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} + \frac{k_{2} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} + \dots + \frac{k_{p} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = \frac{(k_{1} + k_{2} + \dots + k_{p}) (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} \\ = \frac{n (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = \frac{n!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = (\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}}) . \end{matrix}

Поврзано

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

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

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

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

Предлошка:Портал

Предлошка:Математички полиња

Предлошка:Нормативна контрола

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

Содржина

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

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

Воопштување

Поврзано

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

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

Прегледник

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

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

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

Воопштување

Поврзано

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

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

Прегледник

Пребарај