Формула на триъгълника на Паскал с примери
Сара Чен
⚡ Умно обобщение
Триъгълникът на Паскал е триъгълна подредба на числа, където всяка стойност е равна на сумата от двете числа директно над нея, разкривайки дълбоки модели в комбинаториката, биномиалните разложения и вероятностите, които са очаровали математиците от векове.
Какво представлява триъгълникът на Паскал?
Триъгълникът на Паскал е триъгълен масив от числа, който следва прост модел, базиран на реда над него. Популяризиран е от френския математик Блез Паскал през 17-ти век. Триъгълникът започва с една „1“ в горната част и всеки следващ ред също започва и завършва с „1“.
Освен елегантната си форма, триъгълникът на Паскал кодира дълбоки математически зависимости. Той е тясно свързан с биномната теорема, комбинаторното броене и вероятностите, поради което се появява в класните стаи по алгебра, статистика и компютърни науки по целия свят.
История на триъгълника на Паскал
Въпреки че е кръстен на Блез Паскал, триъгълникът го предшества с векове. Китайският математически текст „Деветте глави за математическото изкуство“ съдържа един от най-ранните известни примери, показващ много от същите модели, които използваме днес.
Персийски математик Ал-Караджи и индийски учен PingАла също изследва подобни масиви. Паскал формализира свойствата на триъгълника в своя трактат от 1654 г. „Traité du triangle arithmétique“, който дава на структурата съвременното ѝ име в западната математика.
Построяване на триъгълника на Паскал
Построяването на триъгълника на Паскал е лесно. Единственото правило, което трябва да се запомни, е, че всеки ред започва и завършва с 1, а всяко друго число се изгражда от горния ред.
За всеки ред r и колона c, стойността е равна на сумата от числата в колони c-1 и c на ред r-1.
Тук
- r = 3, 4, 5, …
- n и c = 2, 3, 4, …, r-1.
Ето стъпките за изграждане на триъгълника на Паскал:
Стъпка 1) Започнете, като попълните първите два реда.
Стъпка 2) Вторият елемент на третия ред е сумата от първото и второто число във втория ред.
Стъпка 3) Четвъртият ред започва с „1“. Второто число е 3, което е сборът от 1 и 2 (маркирано в синьо).
Изображението по-долу показва как да попълните четвъртия ред:
Стъпка 4) Петият ред се състои от пет числа. Вече знаем модела за попълване на редовете от предишните стъпки.
Формула на триъгълника на Паскал – Биномен коефициент
Биномиалният коефициент отчита броя начини за избор на подмножество от k елемента от колекция от n елемента. Обикновено се записва като „C(n, k)“ или „n избира k“.
Биномиалният коефициент се определя като:
Символът „!“ обозначава факториела на число.
n! = n.(n-1)(n-2)…3.2.1
Например,
5! = 5.4.3.2.1
= 120
Така че, C(5, 3) или „5 избира 3“ = 5! / 3!(5-3)!
= 120/12
= 10
Метод 1: Изграждане на триъгълника на Паскал по предишния ред
Процедурата тук отразява начина, по който начертахме триъгълника ръчно. Да предположим, че искаме да генерираме триъгълника на Паскал до седем реда.
Стъпките за това са следните:
Стъпка 1) Започнете най-горния ред с „1“.
Стъпка 2) За ред „r“, елементът „c“ ще бъде сумата от колона „c-1“ и колона „c“ на ред „r-1“.
Стъпка 3) Първото и последното число във всеки ред винаги ще бъдат „1“.
Следването на тези три прости стъпки ни позволява систематично да изградим целия триъгълник.
C++ Code на триъгълника на Паскал по предишния ред
#include <bits/stdc++.h> using namespace std; void printRow(int n) { int numbers[n][n]; for (int row = 0; row < n; row++) { for (int col = 0; col <= row; col++) { if (col == 0 || col == row) { numbers[row][col] = 1; } else { numbers[row][col] = numbers[row - 1][col - 1] + numbers[row - 1][col]; } cout << numbers[row][col] << "\t"; } cout << endl; } } int main() { int n; cout << "How many rows: "; cin >> n; printRow(n); }
Изход:
How many rows: 7 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
Python Code Формула на триъгълника на Паскал по предишния ред
def printRow(n): numbers = [[0 for row in range(n)] for col in range(n) ] for row in range(len(numbers)): for col in range(0, row+1): if row == col or col == 0: numbers[row][col] = 1 else: numbers[row][col] = numbers[row-1][col-1]+numbers[row-1][col] print(numbers[row][col],end="\t") print("\n") n = int(input("How many rows: ")) printRow(n)
Примерен изход за триъгълника на Паскал:
How many rows: 7 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
Анализ на сложността
A двумерен масив се използва в тази имплементация. Като се има предвид, че N е броят на редовете в триъгълника на Паскал, това изисква N2 единични пространства. Следователно, сложността на пространството е O(N2).
Функцията използва два вложени цикъла, всеки от които се изпълнява до „N“ пъти. Така че, времевата сложност също е НА2), или квадрат на времевата сложност.
Метод 2: Построяване на триъгълника на Паскал чрез изчисляване на биномиален коефициент
Можем да изведем числата на триъгълника на Паскал директно, използвайки биномни коефициенти. Диаграмата по-долу илюстрира връзката:
Ето стъпките за изграждане на триъгълника на Паскал чрез изчисляване на биномиален коефициент:
Стъпка 1) Най-горният ред е C(0, 0). Използвайки формулата по-горе, C(0, 0) = 1, защото 0! = 1.
Стъпка 2) За ред „i“ ще има общо „i“ елемента. Всеки елемент се изчислява като C(n, r), където n е i-1.
Стъпка 3) Повторете стъпка 2 за толкова редове от триъгълника на Паскал, колкото искате да генерирате.
C++ Code Триъгълникът на Паскал чрез биномиален коефициент
#include <iostream> using namespace std; int factorial(int n) { int result = 1; for (int i = 1; i <= n; i++) { result *= i; } return result; } int binomialCoefficient(int n, int r) { int result = 1; if (r > n) { return -1; } result = factorial(n) / (factorial(r) * factorial(n - r)); return result; } void printPascalTriangle(int row) { for (int i = 0; i <= row; i++) { for (int j = 0; j <= i; j++) { cout << binomialCoefficient(i, j) << "\t"; } cout << endl; } } int main() { int n; cout << "Enter row number: "; cin >> n; printPascalTriangle(n); }
Изход:
Enter row number: 9 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
Python Code Триъгълникът на Паскал чрез биномиален коефициент
def factorial(n): result = 1 for i in range(1,n+1): result*=i return result def binomialCoefficient(n,r): result =1 if r>n: return None result = factorial(n) / (factorial(r) * factorial(n - r)) return int(result) def printPascalTriangle(row): for i in range(row+1): for j in range(i+1): print(binomialCoefficient(i, j), end="\t") print() # print(binomialCoefficient(3, 2)) n = int(input("Enter row number: ")) printPascalTriangle(n)
Примерен изход за триъгълника на Паскал:
Enter row number: 8 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1
Анализ на сложността
В тази имплементация се използват три цикъла: един за изчисляване на биномиалния коефициент и още два за итерация през всеки ред и колона. По отношение на броя на редовете, и трите цикъла се изпълняват до „n“ пъти. Следователно, общата времева сложност е O(n3).
Пространствената сложност е константна, защото не съхраняваме никакви междинни резултати. Програмата изчислява всеки елемент в движение и го отпечатва в рамките на ред, така че пространствената сложност намалява до O (1).
Метод 3: Изграждане на триъгълника на Паскал чрез модифициран биномен коефициент
В предишната техника използвахме формулата за биномиален коефициент, за да изчислим всеки елемент. Модифицираният подход извежда C(n, r) директно от C(n, r-1), намалявайки работата с един порядък.
Ето стъпките за изграждане на триъгълника на Паскал чрез модифициран биномиален коефициент:
Стъпка 1) Започнете първия ред с „1“.
Стъпка 2) Изчислете C(n, r), където „n“ е номерът на реда, а „r“ е индексът на колоната. Присвоете тази стойност на променлива C.
Стъпка 3) За изчисляване на следващия коефициент използвайте C * (n – k) / k. Присвоете тази нова стойност обратно на C.
Стъпка 4) Продължете стъпка 3, докато „k“ достигне края на реда. След всяка итерация увеличавайте k с едно.
C++ Code за триъгълника на Паскал чрез модифициран биномиален коефициент
#include <bits/stdc++.h> using namespace std; void printpascalTriangle(int n) { for (int row = 1; row <= n; row++) { int previous_coef = 1; for (int col = 1; col <= row; col++) { cout << previous_coef << "\t"; previous_coef = previous_coef * (row - col) / col; } cout << endl; } } int main() { int n; cout << "How many rows: "; cin >> n; printpascalTriangle(n); }
Изход:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Code за триъгълника на Паскал чрез модифициран биномиален коефициент
def printpascalTriangle(n): for row in range(1, n+1): previous_coef = 1 for col in range(1, row+1): print(previous_coef, end="\t") previous_coef = int(previous_coef*(row-col)/col) print() n = int(input("How many rows: ")) printpascalTriangle(n)
Резултат от моделите на триъгълника на Паскал:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Анализ на сложността
Имплементацията използва два цикъла, всеки от които се изпълнява максимум „n“ пъти, където „n“ е броят на редовете в триъгълника. Така че, времевата сложност е O(n2), време на квадрат.
Що се отнася до пространствената сложност, не ни е необходим масив за съхранение. Използваме само една променлива, за да запазим предишния биномиален коефициент, така че ни е необходимо само едно допълнително пространство. Следователно пространствената сложност е O (1).
Приложение на триъгълника на Паскал
Ето някои практически приложения на триъгълника на Паскал:
Биномни разширения: Коефициентите на всяко биномно разлагане могат да бъдат прочетени директно от триъгълника на Паскал. Ето един пример:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2и + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3и + 6x2y2 + 4xy3 + 1y4 |
Изчисляване на комбинации: Елементите на триъгълника на Паскал съответстват директно на биномни коефициенти. Например, ако имате 6 топки и искате да изберете 3, отговорът е 6C3Можете да намерите тази стойност в 3-тия елемент на 6-тия ред на триъгълника на Паскал.
Вероятност: Триъгълникът на Паскал се използва широко за изчисляване на вероятности при хвърляне на монети, задачи със зарове и други комбинаторни събития, където всеки резултат съответства на биномно разпределение.
Интересни факти за триъгълника на Паскал
Ето някои факти, които ще намерите за интересни за триъгълника на Паскал:
- Сумата от всички елементи във всеки ред винаги е степен на 2.
- Диагоналните суми на редовете генерират редицата на Фибоначи.
- Всеки ред съответства на коефициентите в разлагането на (a+b)n.
- Ако защриховате само нечетните числа, получената фигура образува фрактала на триъгълника на Серпински.
