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

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

${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 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.