Số Stirling loại hai là gì?
Số Stirling loại hai, ký hiệu \(S(n,k)\) (đôi khi viết là {n trên k} hoặc \(S_2(n,k)\)), đếm số cách phân hoạch một tập hợp gồm n phần tử có nhãn (phân biệt được) thành đúng k tập con không rỗng và không có nhãn (gọi là các khối). Công cụ này tính toàn bộ một hàng: với một giá trị n cố định, nó liệt kê \(S(n,k)\) cho k = 0, 1, 2, ..., n — tức là mọi giá trị trong hàng n của tam giác Stirling. Đây là một đại lượng tổ hợp thuần túy trong toán học, không phụ thuộc vào quốc gia hay vùng miền nào.
Cách sử dụng
Bạn chỉ cần nhập một số nguyên không âm n (số phần tử trong tập hợp) rồi bấm tính. Công cụ sẽ trả về một bảng hai cột gồm k và \(S(n,k)\), cùng với tổng của cả hàng — chính là số Bell \(B(n)\), một cách kiểm tra kết quả rất tiện lợi. Mọi giá trị đều được tính bằng số nguyên độ chính xác tùy ý, nên kết quả luôn chính xác tuyệt đối ngay cả khi chúng lớn vượt xa giới hạn của số 64-bit (điều này xảy ra vào khoảng n = 20-25).
Giải thích công thức
Phương pháp đáng tin cậy nhất là dùng công thức truy hồi
$$S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1)$$xây dựng dần từ trường hợp cơ sở \(S(0,0) = 1\). Các giá trị biên gồm: \(S(n,0) = 0\) với \(n \ge 1\), \(S(n,n) = 1\), \(S(n,1) = 1\) với \(n \ge 1\), và \(S(n,k) = 0\) khi \(k > n\). Ngoài ra còn có công thức dạng tường minh
$$S(n,k) = \frac{1}{k!} \cdot \sum (-1)^{k-j} \binom{k}{j} j^n$$nhưng khi tính bằng số thực dấu phẩy động, công thức này dễ bị sai số lớn do triệt tiêu, nên chúng tôi dùng công thức truy hồi với số nguyên chính xác.
Ví dụ minh họa (n = 5)
Hàng 5 là: k=0 → 0, k=1 → 1, k=2 → 15, k=3 → 25, k=4 → 10, k=5 → 1. Kiểm tra từ hàng 4 = [0,1,7,6,1]: \(S(5,2) = 2\cdot 7 + 1 = 15\), \(S(5,3) = 3\cdot 6 + 7 = 25\), \(S(5,4) = 4\cdot 1 + 6 = 10\). Tổng cả hàng là \(0+1+15+25+10+1 = 52\), đúng bằng số Bell \(B(5) = 52\).
Câu hỏi thường gặp
Vì sao \(S(n,0) = 0\) với \(n \ge 1\)? Bạn không thể phân hoạch một tập hợp không rỗng thành không khối nào; chỉ có tập rỗng mới có phân hoạch rỗng, nên \(S(0,0) = 1\).
Tổng của hàng là gì? Cộng tất cả \(S(n,k)\) theo k sẽ cho ra số Bell \(B(n)\), tức tổng số cách phân hoạch một tập hợp gồm n phần tử.
n có thể lớn đến mức nào? Công cụ này cho phép n lên đến 200; các giá trị trở nên cực kỳ lớn nhưng vẫn chính xác hoàn toàn nhờ phép tính số nguyên lớn.
