Топ-100
Back

ⓘ Правило на Паскал. Правилото на Паскал е математическо равенство, отнасящо се до биномните коефициенти. Според това правило: n − 1 k + n − 1 k − 1 = n k {\displ ..




                                     

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

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

n − 1 k + n − 1 k − 1 = n k {\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k}}

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

                                     

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

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

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

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

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

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

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

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

n − 1 k + n − 1 k − 1 = {\displaystyle {n-1 \choose k}+{n-1 \choose k-1}=} = n − 1! k! n − 1 − k! + n − 1! k − 1! n − 1 − k − 1)! = {\displaystyle ={n-1! \over k!n-1-k!}+{n-1! \over k-1!n-1-k-1)!}=} = n − 1! k! n − 1 − k! + n − 1! k − 1! n − k)! {\displaystyle ={n-1! \over k!n-1-k!}+{n-1! \over k-1!n-k)!}}

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

n − 1! 1 k! n − 1 − k! + 1 k − 1! n − k)!) = {\displaystyle n-1!\left{1 \over k!n-1-k!}+{1 \over k-1!n-k)!}\right)=} = n − 1! n − k k! n − k! + k k! n − k)!) = {\displaystyle =n-1!\left{n-k \over k!n-k!}+{k \over k!n-k)!}\right)=} = n − 1! k! n − k! = n! k! n − k! {\displaystyle ={nn-1! \over k!n-k!}={n! \over k!n-k!}}, което е по определение n k {\displaystyle {n \choose k}}, което и трябваше да докажем.