Трикутник Паскаля – формула, шаблони та приклади
Сара Чен
Що таке трикутник Паскаля?
Трикутник Паскаля — це трикутний масив чисел, за яким слід певний шаблон і з’єднання з рядком перед ним. Його винайшов Блез Паскаль. Цей трикутник починається з одного елемента в першому рядку. Після цього кожен рядок починається і закінчується цифрою «1».
Історія трикутника Паскаля
Китайська книга «Дев'ять глав про математичне мистецтво» містить один із перших прикладів трикутника Паскаля. Крім того, він містить деякі з тих самих візерунків і якостей, які можна знайти в сьогоднішніх трикутниках.
Паскаль був одним із кількох людей у Європі, які вивчали трикутник. До нього інші математики досліджували подібні трикутні масиви чисел.
Побудова трикутника Паскаля
Побудувати трикутник Паскаля просто. Єдине, що вам потрібно пам’ятати, це те, що рядок починається і закінчується на 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++ Код трикутника Паскаля за попереднім рядком
#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 Код формули трикутника Паскаля за попереднім рядком
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 — це кількість рядків у трикутнику Паскаля. Для цього знадобиться Н2 одиничні простори. Тому 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++ Закодуйте трикутник Паскаля біноміальним коефіцієнтом
#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 Закодуйте трикутник Паскаля біноміальним коефіцієнтом
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» разів. Отже, загальна часова складність буде 0(n3).
Складність простору тепер стала постійною, оскільки ми не зберігаємо жодних даних у сховищі. Програма обчислює елемент, і він друкується в рядку. Тоді складність простору зменшується до 0(1).
Спосіб 3: Побудова трикутника Паскаля за модифікованим біноміальним коефіцієнтом
У попередній методиці ми вже бачили, як використовувати біноміальний коефіцієнт для обчислення кожного елемента трикутника Паскаля. Цей підхід визначить C(n,r) з C. (n, r-1). Це спростить справу одним замовленням.
Ось кроки для побудови трикутника Паскаля за модифікованим біноміальним коефіцієнтом:
Крок 1) Почніть перший рядок з «1»
Крок 2) Обчисліть C(n,r), де «n» — номер рядка, а «r» — стовпець або елемент. Присвоїти значення змінній C.
Крок 3) Для обчислення C(n,k) це буде C*(nk)/k. Тепер призначте це значення C.
Крок 4) Продовжуйте крок 3, поки «k» не досягне кінця ряду. Після кожної ітерації збільшуйте значення K на одиницю.
C++ Код для трикутника Паскаля за допомогою модифікованого біноміального коефіцієнта
#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 код для трикутника Паскаля за модифікованим біноміальним коефіцієнтом
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.
- Діагональна сума елементів рядків породжує послідовність Фібоначчі.
Підсумки
- Трикутник Паскаля дає коефіцієнти для біноміальних розкладів.
- Кожен рядок трикутника Паскаля починається і закінчується цифрою «1». Проміжні значення є сумою двох елементів попереднього рядка.
- Діагональне додавання всіх елементів у трикутнику Паскаля дасть вам Послідовність Фібоначчі.
- Трикутник Паскаля також можна створити за допомогою біноміальних коефіцієнтів.
