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

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

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

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

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

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

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

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

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

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

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

, което искахме и да докажем.

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

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

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

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

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

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

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

= \frac{n (n - 1)!}{k! (n - k)!} = \frac{n!}{k! (n - k)!}

, което е по определение

(\binom{n}{k})

, което и трябваше да докажем.

Вижте също

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

Шаблон:Превод от

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

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

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

Вижте също

Навигация

Търсене