Số Stirling loại hai là gì?
Số Stirling loại hai, ký hiệu \(S(n,k)\), cho biết số cách phân chia một tập hợp gồm n phần tử khác nhau (có nhãn) thành đúng k tập con không rỗng và không phân biệt thứ tự. Đây là một đại lượng nền tảng trong tổ hợp, xuất hiện trong nhiều bài toán liên quan đến phân hoạch tập hợp, toàn ánh (surjection) và số Bell. Đây là công cụ toán học thuần túy, hoạt động giống nhau ở mọi nơi.
Cách sử dụng máy tính
Nhập kích thước tập hợp n và số tập con k. Cả hai đều phải là số nguyên không âm. Bấm tính để nhận \(S(n,k)\) — số phân hoạch chính xác. Nếu k lớn hơn n, kết quả là 0, vì bạn không thể lấp đầy nhiều tập con không rỗng hơn số phần tử đang có.
Giải thích công thức
Dạng tường minh là $$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} j^{n}$$ trong đó \(C(k,j)\) là hệ số nhị thức. Một cách tương đương và an toàn hơn về mặt số học là công thức truy hồi $$S(n,k) = k\,S(n-1,k) + S(n-1,k-1)$$ với các trường hợp cơ sở \(S(0,0)=1\), \(S(n,0)=0\) khi \(n>0\), và \(S(0,k)=0\) khi \(k>0\). Máy tính này dùng công thức truy hồi để tránh sai số khử do dấu phẩy động. Một vài trường hợp đặc biệt hữu ích: \(S(n,1)=1\), \(S(n,n)=1\), và \(S(n,2)=2^{n-1}-1\).
Ví dụ minh họa
Với \(n=5\) và \(k=2\): dùng trường hợp đặc biệt, $$S(5,2)=2^{5-1}-1=16-1=15$$ Công thức truy hồi cũng xác nhận điều này: $$S(5,2)=2\cdot S(4,2)+S(4,1)=2\cdot 7+1=15$$ Vậy có 15 cách chia một tập hợp 5 phần tử thành hai nhóm không rỗng.
Câu hỏi thường gặp
Vì sao \(S(0,0)=1\)? Theo quy ước, tập rỗng có đúng một cách phân hoạch thành không phần nào: chính là phân hoạch rỗng.
Điều gì xảy ra khi \(k > n\)? Kết quả bằng 0, vì mỗi tập con đều phải không rỗng mà bạn lại có quá ít phần tử.
Số này liên hệ thế nào với số Bell? Cộng \(S(n,k)\) theo mọi k từ 0 đến n sẽ cho số Bell \(B(n)\), tức tổng số phân hoạch của một tập hợp n phần tử.
