Công thức tam giác Pascal kèm ví dụ
Sarah Chen
⚡ Tóm tắt thông minh
Tam giác Pascal là một sự sắp xếp các số theo hình tam giác, trong đó mỗi giá trị bằng tổng của hai số nằm ngay phía trên nó, hé lộ những quy luật sâu sắc trong tổ hợp, khai triển nhị thức và xác suất, những điều đã thu hút các nhà toán học trong nhiều thế kỷ.
Tam giác Pascal là gì?
Tam giác Pascal là một dãy số hình tam giác tuân theo một quy luật đơn giản dựa trên hàng phía trên nó. Nó được nhà toán học người Pháp Blaise Pascal phổ biến vào thế kỷ 17. Tam giác bắt đầu với một số “1” duy nhất ở đỉnh, và mỗi hàng tiếp theo cũng bắt đầu và kết thúc bằng số “1”.
Ngoài hình dạng thanh lịch, tam giác Pascal còn chứa đựng những mối quan hệ toán học sâu sắc. Nó gắn liền với định lý nhị thức, phép đếm tổ hợp và xác suất, đó là lý do tại sao nó xuất hiện trong các lớp học đại số, thống kê và khoa học máy tính trên toàn thế giới.
Lịch sử tam giác Pascal
Mặc dù được đặt theo tên của Blaise Pascal, hình tam giác đã xuất hiện trước ông hàng thế kỷ. Văn bản toán học Trung Quốc "Cửu chương về nghệ thuật toán học" chứa một trong những ví dụ sớm nhất được biết đến, thể hiện nhiều quy luật tương tự mà chúng ta sử dụng ngày nay.
Nhà toán học người Ba Tư Al-Karaji và học giả người Ấn Độ PingAla cũng đã nghiên cứu các mảng tương tự. Pascal đã chính thức hóa các thuộc tính của tam giác trong luận văn năm 1654 của ông, "Traité du triangle arithmétique", tác phẩm đã đặt tên hiện đại cho cấu trúc này trong toán học phương Tây.
Xây dựng tam giác Pascal
Việc dựng tam giác Pascal khá đơn giản. Quy tắc duy nhất cần nhớ là mỗi hàng bắt đầu và kết thúc bằng số 1, và mọi số khác được tạo thành từ hàng phía trên.
Với bất kỳ hàng r và cột c nào, giá trị bằng tổng của các số trong cột c-1 và cột c của 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 thông tin vào hai hàng đầu tiên.
Bước 2) Phần tử thứ hai của hàng thứ ba là tổng của số thứ nhất và số thứ hai trong hàng thứ hai.
Bước 3) Hàng thứ tư bắt đầu bằng số “1”. Số thứ hai là 3, là tổng của 1 và 2 (được tô màu xanh).
Hình ảnh bên dưới minh họa cách điền vào hàng thứ tư:
Bước 4) Hàng thứ năm gồm năm số. Chúng ta đã biết quy luật điền số vào 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 đếm số cách chọn một tập con gồm k phần tử từ một tập hợp gồm n phần tử. Nó thường được viết là “C(n, k)” hoặc “n chọn k”.
Hệ số nhị thức được định nghĩa như sau:
Ký hiệu “!” biểu thị giai thừa của một số.
n! = n.(n-1).(n-2)…3.2.1
Ví dụ,
5! = 5.4.3.2.1
= 120
Vậy, C(5, 3) hay “5 chọn 3” = 5! / 3!(5-3)!
= 120/12
= 10
Phương pháp 1: Xây dựng tam giác Pascal dựa trên hàng trước đó
Quy trình ở đây tương tự như cách chúng ta vẽ tam giác bằng tay. Giả sử chúng ta muốn tạo ra tam giác Pascal với tối đa bảy hàng.
Các bước để làm như sau:
Bước 1) Bắt đầu hàng trên cùng với số “1”.
Bước 2) Đối với hàng “r”, phần tử “c” sẽ là tổng của cột “c-1” và cột “c” của hàng “r-1”.
Bước 3) Số đầu tiên và số cuối cùng trong mỗi hàng luôn luôn là “1”.
Bằng cách làm theo ba bước đơn giản này, chúng ta có thể xây dựng toàn bộ tam giác một cách có hệ thống.
C++ Code 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 Code Công thức tam giác Pascal của 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 cách triển khai này. Vì N là số hàng trong tam giác Pascal, nên điều này yêu cầu N.2 không gian đơn vị. Do đó, độ phức tạp không gian là O(N2).
Hàm này sử dụng hai vòng lặp lồng nhau, mỗi vòng lặp chạy tối đa “N” lần. Do đó, độ phức tạp về thời gian cũng là N. TRÊN2)hoặc độ phức tạp thời gian bình phương.
Phương pháp 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ể suy ra các số trong tam giác Pascal trực tiếp bằng cách sử dụng hệ số nhị thức. Sơ đồ dưới đây minh họa mối quan hệ này:
Dưới đây là các bước để xây dựng Tam giác Pascal bằng cách tính hệ số nhị thức:
Bước 1) Hàng trên cùng là C(0, 0). Sử dụng công thức trên, C(0, 0) = 1, vì 0! = 1.
Bước 2) Đối với hàng “i”, sẽ có tổng cộng “i” phần tử. Mỗi mục được tính là C(n, r), trong đó n là i-1.
Bước 3) Lặp lại bước 2 cho đến khi tạo được số hàng của tam giác Pascal tùy ý.
C++ Code Tam giác Pascal bằng 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 Code Tam giác Pascal bằng 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
Trong cách triển khai này, có ba vòng lặp được sử dụng: một vòng lặp để tính hệ số nhị thức và hai vòng lặp khác để lặp qua từng hàng và cột. Xét về số lượng hàng, cả ba vòng lặp đều chạy tối đa “n” lần. Do đó, độ phức tạp thời gian tổng thể là O(n²).3).
Độ phức tạp không gian là hằng số vì chúng ta không lưu trữ bất kỳ kết quả trung gian nào. Chương trình tính toán từng phần tử ngay lập tức và in chúng trong cùng một hàng, do đó độ phức tạp không gian giảm xuống còn... O (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 đây, chúng ta đã sử dụng công thức hệ số nhị thức để tính toán từng phần tử. Phương pháp được sửa đổi này suy ra C(n, r) trực tiếp từ C(n, r-1), giảm khối lượng công việc đi một bậc.
Dưới đây là các bước để xây dựng Tam giác Pascal bằng hệ số nhị thức được sửa đổi:
Bước 1) Bắt đầu hàng đầu tiên với số “1”.
Bước 2) Tính C(n, r), trong đó “n” là số hàng và “r” là chỉ số cột. Gán giá trị đó cho biến C.
Bước 3) Để tính hệ số tiếp theo, sử dụng C * (n – k) / k. Gán giá trị mới này trở lại cho C.
Bước 4) Tiếp tục bước 3 cho đến khi “k” đạt đến cuối hàng. Sau mỗi lần lặp, tăng k lên một.
C++ Code cho Tam giác Pascal bằng Hệ số nhị thứ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 Code cho Tam giác Pascal bằng Hệ số nhị thứ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
Phương pháp triển khai sử dụng hai vòng lặp, mỗi vòng lặp chạy tối đa “n” lần, trong đó “n” là số hàng trong tam giác. Do đó, độ phức tạp thời gian là Trên2), bình phương thời gian.
Về độ phức tạp không gian, chúng ta không cần bất kỳ mảng nào để lưu trữ. Chúng ta chỉ sử dụng một biến để lưu giữ hệ số nhị thức trước đó, vì vậy chúng ta chỉ cần thêm một ô nhớ. Do đó, độ phức tạp không gian là O (1).
Ứng dụng tam giác Pascal
Dưới đây là một số ứng dụng thực tế của Tam giác Pascal:
Khai triển nhị thức: Các hệ số của bất kỳ khai triển nhị thức nào đều có thể được đọc trực tiếp từ tam giác Pascal. Dưới đâ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: Các phần tử của tam giác Pascal tương ứng trực tiếp với các hệ số nhị thức. Ví dụ, nếu bạn có 6 quả bóng và muốn chọn 3 quả, câu trả lời là 6C3Bạn có thể tìm thấy giá trị đó ở phần tử thứ 3 của hàng thứ 6 trong tam giác Pascal.
Xác suất: Tam giác Pascal được sử dụng rộng rãi để tính toán xác suất trong các phép tung đồng xu, bài toán xúc xắc và các sự kiện tổ hợp khác mà mỗi kết quả tương ứng với một phân phối nhị thức.
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ủa tất cả các phần tử trong bất kỳ hàng nào luôn là lũy thừa của 2.
- Tổng các phần tử trên đường chéo của các hàng tạo thành dãy Fibonacci.
- Mỗi hàng tương ứng với các hệ số trong khai triển của (a+b)n.
- Nếu bạn chỉ tô màu các số lẻ, hình thu được sẽ tạo thành hình fractal tam giác Sierpinski.
