Nhấn vào đây để đọc bằng ngôn ngữ khác: English
Trong toán học, tam giác Pascal là một mảng tam giác của hệ số nhị thức.
Các hàng của tam giác Pascal thường được đánh số từ hàng n = 0 ở phía trên cùng (hàng 0). Các phần tử trong mỗi hàng được đánh số từ trái sang phải, bắt đầu từ k = 0 và thường được xếp lệch so với các số trong các hàng liền kề. Tam giác có thể được xây dựng theo cách sau: Ở hàng 0 (hàng trên cùng), có một phần tử duy nhất khác 0 là 1. Mỗi phần tử của mỗi hàng tiếp theo được xây dựng bằng cách cộng số phía trên bên trái với số phía trên bên phải, coi các phần tử trống như 0. Ví dụ, số ban đầu trong hàng đầu tiên (hoặc bất kỳ hàng nào khác) là 1 (tổng của 0 và 1), trong khi số 1 và 3 trong hàng thứ ba được cộng lại để tạo ra số 4 trong hàng thứ tư.
Phần tử ở hàng thứ n và cột thứ k của tam giác Pascal được ký hiệu là 
0 trong hàng trên cùng là 
Với ký hiệu này, việc xây dựng trong đoạn trước có thể được viết như sau:
cho mọi số nguyên không âm n và mọi số nguyên k nằm giữa 0 và n, bao gồm cả 0 và n.
Chúng ta biết rằng phần tử thứ i trong hàng số lineNumber là Hệ số nhị thức C(lineNumber, i) và tất cả các hàng bắt đầu với giá trị 1. Ý tưởng là tính C(lineNumber, i) bằng cách sử dụng C(lineNumber, i-1). Nó có thể được tính trong thời gian O(1) bằng cách sau:
C(lineNumber, i) = lineNumber! / ((lineNumber - i)! * i!)
C(lineNumber, i - 1) = lineNumber! / ((lineNumber - i + 1)! * (i - 1)!)
Chúng ta có thể suy ra biểu thức sau từ hai biểu thức trên:
C(lineNumber, i) = C(lineNumber, i - 1) * (lineNumber - i + 1) / i
Vì vậy, C(lineNumber, i) có thể được tính từ C(lineNumber, i - 1) trong thời gian O(1).