Máy tính số Stirling

Chào mừng bạn đến với Máy tính số Stirling, một công cụ tổ hợp toàn diện để tính toán số Stirling loại thứ nhất (không dấu — hoán vị thành chu trình) và loại thứ hai (phân hoạch tập hợp thành các tập con không rỗng). Với các hình ảnh tam giác trực quan tương tác, các bước truy hồi từng bước, biểu đồ cột phân phối và các diễn giải tổ hợp sâu sắc, máy tính này được thiết kế cho sinh viên, giáo viên, nhà nghiên cứu và lập trình viên thi đấu, những người cần kết quả nhanh chóng, chính xác cùng bối cảnh giáo dục.

Số Stirling là gì?

Số Stirling là hai họ số phát sinh tự nhiên trong tổ hợp, đại số và giải tích. Được đặt theo tên nhà toán học người Scotland James Stirling (1692–1770), chúng đóng vai trò là cầu nối giữa giai thừa, hệ số nhị thức và các đồng nhất thức đa thức. Mặc dù chúng ít được biết đến hơn tam giác Pascal, nhưng chúng cũng cơ bản không kém và xuất hiện xuyên suốt trong toán học rời rạc.

Số Stirling loại thứ nhất

Các số Stirling loại thứ nhất không dấu, ký hiệu là \(|s(n,k)|\) hoặc \(\left[{n \atop k}\right]\), đếm số lượng hoán vị của \(n\) phần tử được phân rã thành đúng \(k\) chu trình rời nhau.

Trực giác: Hãy xem xét phần tử thứ \(n\) sẽ đi về đâu. Hoặc nó được chèn vào một trong các chu trình hiện có (có \(n-1\) vị trí để chèn, một vị trí trước mỗi trong số \(n-1\) phần tử khác) — đóng góp số hạng \((n-1)\cdot|s(n-1,k)|\) — hoặc nó tự tạo thành một chu trình mới có độ dài 1, đóng góp \(|s(n-1,k-1)|\).

Các sự kiện chính:

• \(|s(n,1)| = (n-1)!\) — hoán vị vòng quanh (một chu trình lớn)
• \(|s(n,n)| = 1\) — hoán vị đồng nhất (tất cả là điểm cố định)
• \(|s(n,n-1)| = \binom{n}{2}\) — một phép chuyển vị
• \(\sum_{k=0}^{n} |s(n,k)| = n!\) — tổng số hoán vị

Số Stirling loại thứ hai

Các số Stirling loại thứ hai, ký hiệu là \(S(n,k)\) hoặc \(\left\{{n \atop k}\right\}\), đếm số cách để phân hoạch một tập hợp gồm \(n\) phần tử thành đúng \(k\) tập con không rỗng.

Trực giác: Hãy xem xét phần tử thứ \(n\) sẽ đi về đâu. Hoặc nó gia nhập vào một trong \(k\) tập con hiện có (có \(k\) lựa chọn) — đóng góp số hạng \(k \cdot S(n-1,k)\) — hoặc nó tự tạo thành một tập con mới chỉ có một mình nó, đóng góp \(S(n-1,k-1)\).

Các sự kiện chính:

• \(S(n,1) = 1\) — chỉ có một cách: tất cả các phần tử trong một tập
• \(S(n,n) = 1\) — chỉ có một cách: mỗi phần tử là một tập con đơn lẻ
• \(S(n,2) = 2^{n-1} - 1\) — các cách để chia thành hai tập con không rỗng
• \(S(n,n-1) = \binom{n}{2}\) — chọn cặp nào dùng chung một tập con
• \(\sum_{k=0}^{n} S(n,k) = B(n)\) — số Bell thứ \(n\)

Công thức tường minh (Loại thứ hai)

Cách sử dụng máy tính này

1. Nhập n: Tổng số phần tử (0 đến 200).
2. Nhập k: Số lượng chu trình (Loại thứ nhất) hoặc tập con (Loại thứ hai), với 0 ≤ k ≤ n.
3. Chọn loại: Chọn loại thứ nhất, loại thứ hai hoặc cả hai để so sánh song song.
4. Tính toán: Nhấp vào "Tính toán số Stirling" để xem kết quả với các bước thực hiện, hình ảnh tam giác và biểu đồ phân phối.

So sánh: Loại thứ nhất và Loại thứ hai

Ứng dụng của số Stirling

Chuyển đổi đa thức

Số Stirling kết nối các cơ sở đa thức khác nhau:

• Giai thừa tăng: \(x^{(n)} = \sum_{k} |s(n,k)|\, x^k\)
• Lũy thừa thông thường: \(x^n = \sum_{k} S(n,k)\, x^{\underline{k}}\) (giai thừa giảm)

Xác suất và Thống kê

Số Stirling xuất hiện trong việc tính toán momen của các phân phối xác suất, đặc biệt là khi chuyển đổi giữa momen thông thường và momen giai thừa. Chúng rất cần thiết trong phân tích các hoán vị ngẫu nhiên và các bài toán xếp chỗ (occupancy problems).

Khoa học máy tính

Trong phân tích thuật toán, số Stirling xuất hiện trong việc đếm số cách phân phối các đối tượng vào các thùng chứa, phân tích bảng băm và nghiên cứu các hoán vị ngẫu nhiên. Loại thứ hai liên quan trực tiếp đến việc đếm toàn ánh: số lượng các hàm số từ một tập n phần tử đến một tập k phần tử là \(k!\, S(n,k)\).

Lý thuyết số

Số Stirling kết nối với số Bernoulli, số Harmonic và các đồng nhất thức tổng khác nhau. Chúng xuất hiện trong phép tính sai phân hữu hạn và trong công thức Euler-Maclaurin.

Câu hỏi thường gặp

Số Stirling loại thứ nhất là gì?

Số Stirling loại thứ nhất không dấu, ký hiệu |s(n,k)|, đếm số hoán vị của n phần tử phân rã thành đúng k chu trình rời nhau. Chúng thỏa mãn hệ thức truy hồi |s(n,k)| = (n−1)·|s(n−1,k)| + |s(n−1,k−1)| với |s(0,0)| = 1. Tổng các hàng cho ra n! vì mỗi hoán vị đều có một số chu trình nhất định.

Số Stirling loại thứ hai là gì?

Số Stirling loại thứ hai, ký hiệu S(n,k), đếm số cách phân hoạch một tập hợp n phần tử thành đúng k tập con không rỗng. Chúng thỏa mãn hệ thức truy hồi S(n,k) = k·S(n−1,k) + S(n−1,k−1) với S(0,0) = 1. Tổng các hàng cho ra số Bell B(n).

Sự khác biệt giữa số Stirling loại thứ nhất và loại thứ hai là gì?

Loại thứ nhất (không dấu) đếm hoán vị với k chu trình — thứ tự trong mỗi chu trình là quan trọng. Loại thứ hai đếm phân hoạch tập hợp thành k tập con — thứ tự trong các tập con không quan trọng. Chúng có liên quan thông qua nghịch đảo ma trận.

Số Stirling được dùng như thế nào trong toán học?

Số Stirling xuất hiện trong việc chuyển đổi đa thức giữa giai thừa giảm/tăng và lũy thừa thông thường, trong tính toán momen của phân phối xác suất, trong các đồng nhất thức tổ hợp, lý thuyết số và phân tích thuật toán.

Mối quan hệ giữa số Stirling và số Bell là gì?

Số Bell thứ n, B(n), bằng tổng của tất cả các số Stirling loại thứ hai trong hàng n: B(n) = Σ S(n,k) với k chạy từ 0 đến n. Số Bell đếm tổng số cách phân hoạch một tập hợp n phần tử thành bất kỳ số lượng tập con không rỗng nào.

Có công thức tường minh cho số Stirling không?

Có, loại thứ hai có công thức tường minh qua bao hàm-loại trừ: S(n,k) = (1/k!) Σ (−1)^(k−j) C(k,j) j^n cho j từ 0 đến k. Loại thứ nhất có thể được tính qua truy hồi hoặc qua kết nối với giai thừa tăng.

Tài nguyên bổ sung

• Số Stirling loại thứ nhất - Wikipedia
• Số Stirling loại thứ hai - Wikipedia
• OEIS A008277 - Số Stirling loại thứ hai
• OEIS A130534 - Số Stirling loại thứ nhất không dấu