Máy tính số Stirling loại hai S(n,k)

Máy tính số Stirling loại hai S(n,k)

Đang tăng trưởng AI Skill PRO

Nhập phép tính

Công thức

S(n,k)=1k!∑j=0k(−1)j(kj)(k−j)nS\!\left(\text{n},\,\text{k}\right) = \frac{1}{\text{k}!}\sum_{j=0}^{\text{k}} (-1)^{j}\binom{\text{k}}{j}\left(\text{k}-j\right)^{\text{n}}
Thống kê sử dụng

Quảng cáo

Kết quả

Số Stirling loại hai S(5, 2)
15
cách chia các phần tử có nhãn thành các tập con khác rỗng (Phần tử: 5 · Tập con: 2)
n (kích thước tập hợp) 5
k (tập con) 2
Ký hiệu S(n, k)

Báo lỗi nội dung trang này

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.

Bốn quả bóng có nhãn được chia vào hai hộp không nhãn, minh họa một cách phân hoạch tập hợp
\(S(n,k)\) đếm số cách chia n phần tử có nhãn thành k nhóm không nhãn và không rỗng.

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\).

Quảng cáo

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.

Lưới tam giác các số Stirling nhỏ xếp như tam giác Pascal
Tam giác các giá trị \(S(n,k)\), mỗi giá trị được tạo từ hai số phía trên.

Bảng số Stirling loại hai S(n,k) với n = 0 đến 10

Mỗi ô là số cách phân hoạch một tập hợp gồm n phần tử có nhãn thành đúng k khối không rỗng, không nhãn. Bảng được xây dựng từ hệ thức truy hồi \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\), với \(S(0,0)=1\) và \(S(n,0)=S(0,n)=0\) khi \(n\ge 1\). Các ô trống ứng với \(k>n\), khi đó S(n,k)=0. Cột cuối là tổng hàng, chính là số Bell B(n). Ví dụ, S(10,4) = 34105.

n \ k 0 1 2 3 4 5 6 7 8 9 10 Tổng hàng B(n)
0 1 1
1 0 1 1
2 0 1 1 2
3 0 1 3 1 5
4 0 1 7 6 1 15
5 0 1 15 25 10 1 52
6 0 1 31 90 65 15 1 203
7 0 1 63 301 350 140 21 1 877
8 0 1 127 966 1701 1050 266 28 1 4140
9 0 1 255 3025 7770 6951 2646 462 36 1 21147
10 0 1 511 9330 34105 42525 22827 5880 750 45 1 115975

Kiểm tra một ô bằng hệ thức truy hồi: \(S(6,3)=3\cdot S(5,3)+S(5,2)=3\cdot 25+15=90\). Luôn có \(S(n,1)=1\), \(S(n,2)=2^{n-1}-1\), \(S(n,n-1)=\binom{n}{2}\) và \(S(n,n)=1\).

Quảng cáo

Thuật ngữ và ký hiệu chính

Phân hoạch tập hợp
Cách chia một tập hợp thành các tập con không rỗng, đôi một rời nhau (gọi là các khối) mà hợp của chúng là toàn bộ tập hợp. Thứ tự các khối và thứ tự phần tử trong mỗi khối không quan trọng.
Có nhãn và không nhãn
n phần tử có nhãn (phân biệt được, ví dụ 1, 2, …, n). k tập con không có nhãn: hoán đổi hai khối cho cùng một phân hoạch. Nếu các khối có nhãn, số cách đếm sẽ là k!·S(n,k).
Khối không rỗng
Mỗi tập con trong k tập con phải chứa ít nhất một phần tử. Đó là lý do S(n,0)=0 khi n ≥ 1 và S(n,k)=0 khi k > n.
Ký hiệu S(n,k)
Số Stirling loại hai, còn viết là \(\left\{ n \atop k \right\}\). Được tính bằng \(S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}\).
Số Bell B(n)
Tổng số phân hoạch của một tập gồm n phần tử thành số khối bất kỳ: \(B(n)=\sum_{k=0}^{n}S(n,k)\). Các giá trị đầu tiên là 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975.
Hệ số nhị thức
\(\binom{k}{j}=\frac{k!}{j!\,(k-j)!}\), số cách chọn j phần tử từ k. Nó xuất hiện trong công thức bao hàm–loại trừ ở trên.
Toàn ánh
Hàm từ một tập n phần tử lên một tập k phần tử sao cho mọi phần tử của tập k đều được ánh xạ tới ít nhất một lần. Số hàm như vậy là \(k!\cdot S(n,k)\): chia miền xác định thành k khối, rồi gán các khối cho k đích theo k! cách.

Loại hai và loại một. Số Stirling loại hai đếm các phân hoạch của một tập hợp thành k khối. Số Stirling loại một, viết là \(c(n,k)\) hoặc \(\left[ n \atop k \right]\) (không dấu), đếm các hoán vị của n phần tử có đúng k chu trình. Chúng tuân theo một hệ thức truy hồi khác, \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\), và có liên hệ với loại hai khi là ma trận nghịch đảo của nhau (có dấu).

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ử.

Cập nhật lần cuối:

Phổ biến nhất trong Toán học và Thống kê

Xem tất cả máy tính Toán học và Thống kê