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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

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

Доказателство в рамките на комбинаториката[редактиране | edit source]

Нека да припомним определението за комбинация: {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}, което искахме и да докажем.

Алгебрично доказателство[редактиране | edit source]

{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}, което и трябваше да докажем.

Вижте още[редактиране | edit source]

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