Треугольник Паскаля – формулы, закономерности и примеры
Сара Чен
Что такое треугольник Паскаля?
Треугольник Паскаля — это треугольный массив чисел, за которым следует определенный шаблон и соединение со строкой перед ним. Его изобрел Блез Паскаль. Этот треугольник начинается с одного элемента в первой строке. После этого каждая строка начинается и заканчивается цифрой «1».
История треугольника Паскаля
Китайская книга «Девять глав математического искусства» содержит один из первых примеров треугольника Паскаля. Кроме того, он содержит некоторые из тех же моделей и качеств, которые можно найти в современных треугольниках.
Паскаль был одним из нескольких человек в Европе, изучавших треугольник. До него подобные треугольные массивы чисел исследовали другие математики.
Построение треугольника Паскаля
Построить треугольник Паскаля просто. Единственное, что вам нужно запомнить, это то, что Ряд начинается и заканчивается цифрой 1. Для остальных чисел правило следующее:
Для любой строки r и столбца c число будет равно сумме столбцов c-1 и c из строки r-1.
Здесь,
- г = 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-1). (n-2)…3.2.1
Например,
5! "="
= 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» раз. Таким образом, временная сложность также равна НА2) или квадрат временной сложности.
Метод 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.х + 1.y |
| (х + у)2 | 1x2 + 2ху + 1y2 |
| (х + у)3 | 1x3 + 3x2и + 3xy2 + 1y3 |
| (х + у)4 | 1x4 + 4x3и + 6x2y2 + 4xy3 + 1y4 |
Расчет комбинаций: Мы видели, что элементы треугольника Паскаля эквивалентны биномиальным коэффициентам. Например, если у вас есть 6 шаров и вас попросили выбрать 3 шара, это будет 6C3. Или вы можете найти число в третьем элементе шестой строки треугольника Паскаля.
Интересные факты о треугольнике Паскаля
Вот несколько интересных фактов о треугольнике Паскаля:
- Сумма всех элементов подряд всегда равна степени 2.
- Диагональная сумма элементов строк порождает последовательность Фибоначчи.
Резюме
- Треугольник Паскаля дает коэффициенты для биномиальных разложений.
- Каждая строка треугольника Паскаля начинается и заканчивается цифрой «1». Промежуточные значения представляют собой сумму двух элементов предыдущей строки.
- Сложение всех элементов треугольника Паскаля по диагонали даст вам Последовательность Фибоначчи.
- Треугольник Паскаля также можно построить с помощью биномиальных коэффициентов.
