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

Триъгълникът на Паскал е симетричен числов триъгълник.

Всяко число от даден ред на триъгълника (с изключение на първото-лявото и последното-дясното) е сума от двете числа, разположени на предходния ред на текущата и предходната позиция. Това правило на Паскал лесно се обобщава за пирамида в тримерното пространство и за други n-мерни обобщения на триъгълника.

Намира приложение за лесно изчисляване брой комбинации без повторения, за изчисляване на биномни коефициенти (Нютоновия бином).

Приложената графика илюстрира и други зависимости:

Сумата от елементите на всеки ред е степен на 2 - най-лявата колона. Разглеждат се елементи на триъгълника по колона успоредна на външната лява страна на числовия триъгълник. Сумата от едноцветните елементите по колона, дава поредните числа от реда на Фибоначи - най-дясната колона в графиката. Елементите от всеки ред образуват редица симетрична спрямо средата си и разглеждането на суми от елементи по определена линия вляво или вдясно е еднозначно.

Алгоритми за изчисляване стойност на елемент от триъгълника на Паскал.

Изчисляването на всеки отделен елемент се извършва по формулата за изчисляване на брой комбинации без повторение от определен клас: C = n!/(k! * (n-k)!) = (n-k+1)!/k!. Недостатъци: множеството стойности на факториел вече са били изчислявани; тежка изчислителна задача, в която крайната стойност е много по-малка от стойността на отделните елементи на дробта.

Следващите алгоритми използват рекурентната формула: P(n,k) = P(n-1,k-1) + P(n-1,k).

Използване на двумерен масив, в който се съхраняват стойностите на вече изчислените елементи. Недостатъци: разхитително използване на памет.

Използване на триъгълен масив - идеята, че че началните редове имат по-малък брой елементи от крайните редове в триъгълника. Необходимият обем памет се редуцира двукратно.

Използване на двумерен масив - само с два реда. Използваният обем памет силно намалява за сметка нарастване на изчислителната сложност - на всеки ход на алгоритъма преди започване на изчисляването на ред от триъгълника на Паскал елементите от първия ред от масива приемат стойности на съответните елементи от втория ред, а елементите на втория ред приемат стойност 0.

Чрез мемоизация (memoization-англ. запомняне) съхраняване в паметта резултата от изпълнение на функция с цел предотвратяване повторното й изчисляване. При всяко извикване функцията проверява дали вече не е била стартирана. Ако не е била извиквана функцията се извиква и резултатът й се съхранява; ако се извиква се ползва съхранения резултат.

Мемоизацията е един от начините за увеличаване скоростта на използваните програма и намира приложение в синтактическия анали, кеширането, буферирането на страници в паметта. Основното предимство на този алгоритъм е това, че се пише по-лесно - чрез рекурсия.

При изчисляване елемент от триъгълника на Паскал рекурентната формула: P(n,k) = P(n-1,k-1) + P(n-1,k) може интуитивно да се свърже с формулата за изчисляване елемент от редица на Фибоначи F(n) = F(n-1) + F(n-2). Използваните алгоритми са близки.

Подобни подходи могат да се използват и за изчисляване тримерния случай - пирамида на Паскал с използване на триномни коефициенти.

При решенията на примерните задачи, илюстрирани с екранна снимка, са използвани част от изброените алгоритми, а за втората част, огледално обърнатия триъгълник е приложена опашата рекурсия.

Различията в разгледаните примерни задачи за триъгълник на Паскал могат да бъдат най-общо групирани:

извежда се целочислен остатък на елементите - подобно на триъгълника на Серпински;

промяна на индексите в събираемите (подобно на триъгълника на Каталан) и/или на коефициентите пред събираемите;

промяна стойността на краен елемент на реда с модификации: константна стойност за единия краен елемент (ляв/десен) и стойност от пореден елемент в числова редица, константна стойност за двата крайни елемента (не непременно еднакви), двата крайни елемента приемат стойност от числови редици (не непременно еднакви);

друг вид модифициран триъгълник на Паскал като комбинация от две или повече особености.

Можете да намерите допълнителен материал за триъгълник на Паскал на следните адреси: https://en.wikipedia.org/wiki/Pascal%27s_triangle, http://mathworld.wolfram.com/PascalsTriangle.html.

Разгледайте други основни типове примерни задачи, за чието решение се използват фигури с числа и фигурни числа. Потърсете допълнителен материал за: триъгълник на Hosoya - Фибоначи, триъгълник на Lucas, хармоничен триъгълник на Лайбниц, числа на Stirling, триъгълник на Бернули, факториел, биномен коефициент.