Формула треугольника Паскаля с примерами
Сара Чен
⚡ Умное резюме
Треугольник Паскаля — это треугольное расположение чисел, где каждое значение равно сумме двух чисел, расположенных непосредственно над ним, что выявляет глубинные закономерности в комбинаторике, биномиальных разложениях и теории вероятности, которые веками завораживали математиков.
Что такое треугольник Паскаля?
Треугольник Паскаля — это треугольная матрица чисел, которая следует простому шаблону, основанному на строке выше. Он был популяризирован французским математиком Блезом Паскалем в XVII веке. Треугольник начинается с одной «1» наверху, и каждая последующая строка также начинается и заканчивается «1».
Помимо своей элегантной формы, треугольник Паскаля содержит в себе глубокие математические взаимосвязи. Он тесно связан с биномиальной теоремой, комбинаторным подсчетом и теорией вероятности, поэтому его изучают на уроках алгебры, статистики и информатики по всему миру.
История треугольника Паскаля
Хотя треугольник назван в честь Блеза Паскаля, он существовал за столетия до него. В китайском математическом тексте «Девять глав о математическом искусстве» содержится один из самых ранних известных примеров, демонстрирующий многие из тех же закономерностей, которые мы используем сегодня.
Персидский математик Аль-Караджи и индийский учёный PingАла также исследовал подобные массивы. Паскаль формализовал свойства треугольника в своем трактате 1654 года «Traité du triangle arithmétique», который дал этой структуре ее современное название в западной математике.
Построение треугольника Паскаля
Построение треугольника Паскаля довольно простое. Единственное правило, которое нужно помнить, — каждая строка начинается и заканчивается единицей, а все остальные числа строятся из строки выше.
Для любой строки 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! "="
= 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. Учитывая, что N — это количество строк в треугольнике Паскаля, это требует N.2 Единичные пространства. Следовательно, пространственная сложность составляет O(N).2).
Функция использует два вложенных цикла, каждый из которых выполняется до «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(n).3).
Пространственная сложность постоянна, поскольку мы не храним никаких промежуточных результатов. Программа вычисляет каждый элемент на лету и выводит его в строке, поэтому пространственная сложность сводится к 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.х + 1.y |
| (х + у)2 | 1x2 + 2ху + 1y2 |
| (х + у)3 | 1x3 + 3x2и + 3xy2 + 1y3 |
| (х + у)4 | 1x4 + 4x3и + 6x2y2 + 4xy3 + 1y4 |
Расчет комбинаций: Элементы треугольника Паскаля напрямую соответствуют биномиальным коэффициентам. Например, если у вас есть 6 шаров и вы хотите выбрать 3, ответ будет... 6C3Это значение можно найти в третьем элементе шестой строки треугольника Паскаля.
Вероятность: Треугольник Паскаля широко используется для вычисления вероятностей при подбрасывании монеты, решении задач с игральными костями и других комбинаторных событиях, где каждому исходу соответствует биномиальное распределение.
Интересные факты о треугольнике Паскаля
Вот несколько интересных фактов о треугольнике Паскаля:
- Сумма всех элементов в любой строке всегда является степенью двойки.
- Диагональные суммы строк образуют последовательность Фибоначчи.
- Каждая строка соответствует коэффициентам в разложении (a+b).n.
- Если закрасить только нечётные числа, получится фрактал в виде треугольника Серпинского.
