[AWA2] Số Stirling Loại 2

Định nghĩa: Số phân hợp tập hợp n phần tử thành k khối không rỗng, gọi là số Stirling loại 2, kí hiệu S(n, k). Nói cách khác, số Stirling loại 2 là số cách phân phối n quả bóng phân biệt vào k hộp giống nhau mà không có hộp nào rỗng.

Công thức tính: Cho n và k là số tự nhiên, ta có: S(n+1, k) = S(n, k-1) + k*S(n, k)

Quy ước: S(n, 0) = 0 với mọi n>0. S(n, k) = 0 nếu k>n và S(0, 0) = 1.

Ta xây dựng bảng sau gồm một số số stirling loại 2:

Áp dụng lý thuyết về số Stirling ta có thể giải bài sau: Chia nhóm

Nguồn: http://vn.spoj.com/problems/BCDIV/

Một hôm trời nắng nóng bức, Chí Phèo nhà ta lại đến nhà Bá kiến đòi tiền mua rượu. Oái oăm thay, tên Bá Kiến keo kiệt hôm nay lại dở chứng bắt Chí phải thực hiện yêu cầu của mình rồi mới cho tiền. Chí tức tối lắm nhưng vì quá ghiền rượu nên hắn đành phải chấp nhận điều kiện mà cụ thể là giải 1 bài toán.

Bài toán có nội dung như sau : Cho n phần tử khác nhau, hỏi có bao nhiêu cách chia n phần tử đó thành k nhóm mà mỗi nhóm có ít nhất 1 phần tử (các hoán vị của các nhóm được xem là 1 cách).

Vì thất học nên Chí nghĩ mãi không ra, các bạn giúp Chí 1 tay nhé, không thì hắn ta chết vì thèm rượu mất ^^

Dữ liệu vào : Dòng đầu tiên chứa số T là số test. T dòng tiếp theo mỗi dòng chứa 2 số N và K, với 1<=K<=N<=25 Dữ liệu ra : T dòng, mỗi dòng là số cách với test tương ứng.

Input: 1 4 2 Output: 7

Giải thích : 7 cách chia đó là (ABC)(D) , (ABD)(C) , (ADC)(B) , (DBC)(A) , (AB)(CD) , (AC)(BD) , (BC)(AD)

Ta tính một bảng số Stirling trước rồi sau đó nhập t, với mỗi n, k ta in giá trị tương ứng trong bảng.

Share this:

• X
• Facebook

Like Loading...