Tam giác Pascal – Công thức, mô hình và ví dụ
Sarah Chen
Tam giác Pascal là gì?
Tam giác Pascal là một dãy số hình tam giác theo sau là một mẫu cụ thể và kết nối với hàng trước nó. Nó được phát minh bởi Blaise Pascal. Tam giác này bắt đầu bằng một phần tử ở hàng đầu tiên. Sau đó, mỗi hàng bắt đầu và kết thúc bằng số “1”.
Lịch sử tam giác Pascal
Cuốn sách Trung Quốc “Cửu chương về nghệ thuật toán học” có một trong những ví dụ đầu tiên về Tam giác Pascal. Ngoài ra, nó còn chứa đựng một số kiểu mẫu và đặc tính tương tự như các hình tam giác ngày nay.
Pascal là một trong số ít người ở Châu Âu đã nghiên cứu về tam giác. Các nhà toán học khác đã nghiên cứu các dãy số tam giác tương tự trước ông.
Xây dựng tam giác Pascal
Việc xây dựng Tam giác Pascal rất đơn giản. Điều duy nhất bạn cần nhớ là Hàng bắt đầu và kết thúc bằng 1. Quy tắc cho các số còn lại như sau:
Đối với bất kỳ hàng r và cột c nào, số này sẽ là tổng của các cột c-1 và c từ Hàng r-1.
Ở đây,
- r = 3,4,5….
- n và c = 2,3,4,…r-1.
Dưới đây là các bước xây dựng Tam giác Pascal:
Bước 1) Hãy bắt đầu bằng cách điền vào hai hàng.
Bước 2) Phần tử thứ hai của dòng thứ ba là tổng của số thứ nhất và số thứ hai ở hàng thứ hai.
Bước 3) Hàng thứ tư sẽ bắt đầu bằng “1.”. Số thứ hai là 3, là tổng của 1 và 2 (được đánh dấu màu xanh lam).
Hình ảnh dưới đây cho thấy cách điền vào Hàng thứ tư:
Bước 4) Hàng thứ năm sẽ bao gồm năm số. Chúng ta đã biết mẫu để điền các hàng từ các bước trước đó.
Công thức tam giác Pascal – Hệ số nhị thức
Hệ số nhị thức là một số biểu thị các phương pháp khác nhau để chọn một tập hợp con gồm k phần tử từ một tập hợp n phần tử. Thông thường, nó được viết là “C(n,k)” hoặc “n choose k.”
Hệ số nhị thức được định nghĩa là
Các "!" biểu thị “giai thừa”.
N! = n.(n-1). (n-2)…3.2.1
Ví dụ,
5! = 5.4.3.2.1
= 120
Vì vậy, giả sử C(5,3) hoặc 5 chọn 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Cách 1: Xây dựng Tam giác Pascal theo hàng trước
Các bước trong quy trình này giống như các bước trong tam giác Pascal. Giả sử chúng ta muốn tạo tam giác Pascal có tối đa bảy hàng.
Các bước để thực hiện được như sau:
Bước 1) Bắt đầu hàng trên cùng với “1”.
Bước 2) Đối với hàng “r”, mục “c” sẽ là tích của “c-1” và “c” là số của hàng “r-1”.
Bước 3) Số đầu tiên và số cuối cùng liên tiếp sẽ luôn là “1”.
Chúng ta phải tuân thủ ba bước đơn giản này để tạo tam giác Pascal.
C++ Mã của tam giác Pascal theo hàng trướ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);
}
Đầu ra:
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 Mã công thức tam giác Pascal theo hàng trước
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)
Ví dụ về tam giác Pascal:
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
Phân tích độ phức tạp
A mảng hai chiều đã được sử dụng trong quá trình thực hiện. Cho rằng N là số hàng trong tam giác Pascal. Điều này sẽ yêu cầu N2 không gian đơn vị. Do đó, O sẽ là độ phức tạp của không gian (N2).
Chúng ta có hai vòng lặp trong hàm, và mỗi vòng lặp chạy trong “N” lần. Vì vậy, độ phức tạp về thời gian cũng là TRÊN2) hoặc độ phức tạp của thời gian bình phương.
Cách 2: Xây dựng Tam giác Pascal bằng cách tính hệ số nhị thức
Chúng ta có thể rút ra một cách đơn giản các số trong tam giác pascal bằng hệ số nhị thức. Đây là sơ đồ:
Dưới đây là các bước để xây dựng Tam giác Pascal bằng cách tính nhị thức:
Bước 1) Hàng trên cùng sẽ là C(0,0). Sử dụng công thức trên cho Hệ số nhị thức, C(0,0) = 1. Vì 0! = 1.
Bước 2) Đối với hàng “i”, sẽ có tổng số phần tử “i”. Mỗi mục sẽ được tính C(n,r) trong đó n sẽ là i-1.
Bước 3) Lặp lại bước 2 để biết số hàng bạn muốn cho tam giác pascal.
C++ Viết tam giác Pascal theo hệ số nhị thứ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);
}
Đầu ra:
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 Viết tam giác Pascal theo hệ số nhị thức
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)
Ví dụ về tam giác Pascal:
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
Phân tích độ phức tạp
Ba vòng lặp được sử dụng trong quá trình triển khai. Một vòng lặp để tính hệ số Binomial và hai vòng lặp còn lại để tạo số cho tất cả các hàng. Về số lượng hàng, chúng ta có ba vòng lặp thực hiện “n” lần. Do đó, độ phức tạp thời gian tổng thể sẽ là 0(n3).
Độ phức tạp của không gian hiện là hằng số vì chúng ta không lưu trữ bất kỳ dữ liệu nào. Chương trình tính toán phần tử và in nó theo hàng. Độ phức tạp của không gian sau đó giảm xuống còn 0(1).
Cách 3: Xây dựng Tam giác Pascal bằng hệ số nhị thức sửa đổi
Trong kỹ thuật trước, chúng ta đã biết cách sử dụng hệ số nhị thức để tính từng phần tử của tam giác Pascal. Cách tiếp cận này sẽ xác định C(n,r) từ C. (n, r-1). Nó sẽ đơn giản hóa mọi thứ theo một thứ tự.
Dưới đây là các bước xây dựng Tam giác Pascal bằng Hệ số nhị thức sửa đổi:
Bước 1) Bắt đầu hàng đầu tiên với “1”
Bước 2) Tính C(n,r), trong đó “n” là số hàng và “r” là cột hoặc phần tử. Gán giá trị cho biến C.
Bước 3) Để tính C(n,k), nó sẽ là C*(nk)/k. Bây giờ, gán giá trị này cho C.
Bước 4) Tiếp tục bước 3 cho đến khi “k” đến cuối Hàng. Sau mỗi lần lặp, tăng giá trị của K lên một.
C++ Mã cho Tam giác Pascal bằng hệ số nhị thức được sửa đổi
#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);
}
Đầu ra:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python mã cho Tam giác Pascal bằng Hệ số nhị thức được sửa đổi
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)
Đầu ra của mô hình tam giác Pascal:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Phân tích độ phức tạp
Việc triển khai có hai vòng lặp. Mỗi vòng lặp chạy tối đa “n” thời gian, trong đó “n” có nghĩa là số hàng trong tam giác pascal. Vì vậy, độ phức tạp về thời gian là Trên2), bình phương thời gian.
Về độ phức tạp của không gian, chúng tôi không cần bất kỳ mảng nào để lưu trữ. Chúng tôi chỉ sử dụng một biến để giữ hệ số nhị thức trước đó. Vì vậy, chúng tôi chỉ cần thêm một không gian. Độ phức tạp của không gian trở thành O (1).
Ứng dụng tam giác Pascal
Sau đây là một số ứng dụng của Tam giác Pascal:
Khai triển nhị thức: Chúng ta có thể xác định hệ số khai triển nhị thức từ tam giác pascal. Đây là một ví dụ:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2và + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3và + 6x2y2 + 4xy3 + 1y4 |
Tính toán tổ hợp: Chúng ta đã thấy các phần tử của tam giác Pascal tương đương với các hệ số nhị thức. Ví dụ, nếu bạn có 6 quả bóng và được yêu cầu chọn 3 quả bóng, nó sẽ là 6C3. Hoặc, bạn có thể tìm số ở phần tử thứ 3 của Hàng thứ 6 trong tam giác Pascal.
Những sự thật thú vị về Tam giác Pascal
Dưới đây là một số sự kiện bạn sẽ thấy thú vị về tam giác Pascal:
- Tổng các phần tử liên tiếp luôn là lũy thừa của 2.
- Tổng theo đường chéo của các phần tử của các hàng tạo ra chuỗi Fibonacci.
Tổng kết
- Tam giác Pascal đưa ra các hệ số cho Khai triển nhị thức.
- Mỗi hàng của tam giác pascal bắt đầu và kết thúc bằng “1”. Các giá trị trung gian là tổng của hai phần tử ở hàng trước.
- Phép cộng theo đường chéo của tất cả các phần tử trong tam giác Pascal sẽ cho bạn kết quả Chuỗi Fibonacci.
- Tam giác Pascal cũng có thể được tạo bằng Hệ số nhị thức.
