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

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

:{n-1\choose k} + {n-1\choose k-1} = {n\choose k}\quad\text{for }1 \le k \le n 

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

:
{n \choose k} + {n \choose k-1} = {n + 1 \choose k} \quad\text{for } 1 \le k \le n + 1


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

## Комбинаторен доказ
мини|Сликовит приказ на комбинаторниот доказ: <math>\binom 4 1+\binom 4 2=\binom 5 2.</math>
Паскаловото правило има интуитивно комбинаторно значење. Ако се потсетиме дека {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{align}
{ 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{align}


## Воопштување
Нека 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{align}
& {} \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{align}


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

## Користена литература
* Merris, Russell. http://media.wiley.com/product_data/excerpt/6X/04712629/047126296X.pdf''Combinatorics''. John Wiley & Sons. 2003 ISBN 978-0-471-26296-1

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

Категорија:Математички идентитети
Категорија:Комбинаторика
жПравило