Công cụ tính số Stirling

Giới thiệu về công cụ này

Số Stirling có hai họ cùng phân rã n đối tượng quanh số nguyên k, nhưng chúng đếm những thứ khác nhau. Số Stirling loại một, s(n,k), đếm các hoán vị của n phần tử tách thành đúng k chu trình rời nhau; số Stirling loại hai, S(n,k), đếm số cách phân hoạch một tập n phần tử thành đúng k tập con khác rỗng, không có thứ tự. Cả hai đều thỏa các hệ thức truy hồi đơn giản — chẳng hạn S(n,k) = k·S(n−1,k) + S(n−1,k−1) — chính là cách máy tính này dựng chúng từ các trường hợp nhỏ hơn.

Sinh viên tổ hợp và toán rời rạc dùng các số này để giải bài toán đếm về cấu trúc chu trình của hoán vị và phân hoạch tập hợp, còn nhà khoa học máy tính áp dụng số Stirling loại hai để phân tích thuật toán nhóm hoặc chia dữ liệu vào các thùng, và trong các công thức chuyển đổi giữa giai thừa giảm và lũy thừa thông thường.