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

Правилото на Паскал е математическо равенство, отнасящо се до биномните коефициенти. Според това правило:

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

Където ${x \choose y}$ е комбинация от y елемента измежду x.

Доказателство в рамките на комбинаториката

Нека да припомним определението за комбинация: ${n \choose k}$ е броят на възможните начини, по които могат да бъдат подредени k елемента, избрани между множество от n елемента.

Нека да обозначим с Х един елемент измежду тези n елемента. Тогава, след всеки път, когато избираме k елемента измежду тези n, има две възможности: или X е в множеството на избраните елементи, или не е.

Първата възможност е Х да е един от избраните елементи, които са общо k. Тогава, останалите елементи могат да бъдат подредени по ${n-1 \choose k-1}$ начина.

Втората възможност е Х да не е от избраните елементи. Тогава останалите елементи могат да бъдат подредени по ${n-1 \choose k}$ начина.

Понеже събитията „Х е сред избраните елементи“ и „Х не е сред избраните елементи“ са несъвместими (т.е. не могат да бъдат верни по едно и също време), ако искаме да получим общия брой възможни подреждания, стига да съберем възможните подреждания в единия или другия случай, или:

${n-1 \choose k}+{n-1 \choose k-1}={n \choose k}$, което искахме и да докажем.

Алгебрично доказателство

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

$={(n-1)! \over k!(n-1-k)!}+{(n-1)! \over (k-1)!(n-1-(k-1))!}=$

$={(n-1)! \over k!(n-1-k)!}+{(n-1)! \over (k-1)!(n-k))!}$

Понеже $(k-1)!={k! \over k}$, както и $(n-1-k)!=(n-k-1)!={\frac {(n-k)!}{n-k}}$, то

$(n-1)!\left({1 \over k!(n-1-k)!}+{1 \over (k-1)!(n-k))!}\right)=$

$=(n-1)!\left({n-k \over k!(n-k)!}+{k \over k!(n-k))!}\right)=$

$={n(n-1)! \over k!(n-k)!}={n! \over k!(n-k)!}$, което е по определение ${n \choose k}$, което и трябваше да докажем.

Вижте също

• Триъгълник на Паскал

Тази страница частично или изцяло представлява превод на страницата Pascal's rule в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​