Формула трикутника Паскаля з прикладами
Сара Чен
⚡ Розумний підсумок
Трикутник Паскаля — це трикутне розташування чисел, де кожне значення дорівнює сумі двох чисел безпосередньо над ним, що розкриває глибокі закономірності в комбінаториці, біноміальних розкладах та теорії ймовірностей, які захоплювали математиків протягом століть.
Що таке трикутник Паскаля?
Трикутник Паскаля — це трикутний масив чисел, який відповідає простому шаблону, що базується на рядку над ним. Його популяризував французький математик Блез Паскаль у 17 столітті. Трикутник починається з однієї «1» зверху, і кожен наступний рядок також починається та закінчується «1».
Окрім своєї елегантної форми, трикутник Паскаля кодує глибокі математичні зв'язки. Він тісно пов'язаний з теоремою біномів, комбінаторним рахуванням та теорією ймовірностей, саме тому його використовують у класах алгебри, статистики та інформатики по всьому світу.
Історія трикутника Паскаля
Хоча названий на честь Блеза Паскаля, трикутник виник на століття раніше за нього. Китайський математичний текст «Дев'ять розділів про математичне мистецтво» містить один із найдавніших відомих прикладів, що демонструє багато тих самих закономірностей, які ми використовуємо сьогодні.
Перський математик Аль-Караджі та індійський вчений PingАла також досліджував подібні масиви. Паскаль формалізував властивості трикутника у своєму трактаті 1654 року «Трактат про арифметику трикутника», який дав цій структурі сучасну назву в західній математиці.
Побудова трикутника Паскаля
Побудова трикутника Паскаля є простою. Єдине правило, яке слід пам'ятати, це те, що кожен рядок починається і закінчується одиницею, а кожне інше число будується з рядка вище.
Для будь-якого рядка 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» разів. Отже, часова складність також O (N2), або квадрат часової складності.
Спосіб 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» – це кількість рядків у трикутнику. Отже, часова складність становить О (н.)2), у квадраті часу.
Щодо просторової складності, нам не потрібен масив для зберігання. Ми використовуємо лише одну змінну для збереження попереднього біноміального коефіцієнта, тому нам потрібен лише один додатковий пробіл. Таким чином, просторова складність дорівнює O (1).
Застосування трикутника Паскаля
Ось деякі практичні застосування трикутника Паскаля:
Біноміальні розширення: Коефіцієнти будь-якого біноміального розкладу можна прочитати безпосередньо з трикутника Паскаля. Ось приклад:
| (х + у)0 | 1 |
| (х + у)1 | 1.x + 1.y |
| (х + у)2 | 1x2 + 2xy + 1y2 |
| (х + у)3 | 1x3 + 3x2та + 3xy2 + 1y3 |
| (х + у)4 | 1x4 + 4x3та + 6x2y2 + 4xy3 + 1y4 |
Розрахунок комбінацій: Елементи трикутника Паскаля безпосередньо відповідають біноміальним коефіцієнтам. Наприклад, якщо у вас є 6 кульок і ви хочете вибрати 3, відповідь така: 6C3Ви можете знайти це значення у 3-му елементі 6-го рядка трикутника Паскаля.
Імовірність: Трикутник Паскаля широко використовується для обчислення ймовірностей у задачах на підкидання монети, гральні кості та інших комбінаторних подіях, де кожен результат відповідає біноміальному розподілу.
Цікаві факти про трикутник Паскаля
Ось деякі факти про трикутник Паскаля, які вас зацікавлять:
- Сума всіх елементів у будь-якому рядку завжди є степенем числа 2.
- Діагональні суми рядків генерують послідовність Фібоначчі.
- Кожен рядок відповідає коефіцієнтам у розкладі (a+b)n.
- Якщо заштрихувати лише непарні числа, отримана фігура утворює фрактал трикутника Серпінського.
