Archive

Posts Tagged ‘Set Theory’

Số bộ các tập con

May 27, 2009 Leave a comment

Bài toán 1.

Tìm số bộ ba các tập con (X, Y, Z) của tập U gồm n phần tử, sao cho

 

(Ký hiệu )

Áp dụng nhận xét ta có

Tương tự với hai điều kiện dưới:

Mà ta biết rằng U có biểu diễn dạng chuẩn tắc giao đầy đủ:


Theo trên thì

Hơn nữa các tập

đều đôi một giao nhau bằng rỗng (mỗi tập có thể bằng rỗng)

Xét ánh xạ sao cho nếu thì , với

Tức là mỗi bộ có thứ tự thì ứng với duy nhất ánh xạ xác định như trên.
Ngược lại với mỗi ánh xạ thì ứng với duy nhất một bộ có thứ tự
.Chú ý tính chất của ánh xạ thì với .

Như vậy ta đã thiết lập một song ánh từ tập các bộ 5 các tập con trong đó với vào tập các ánh xạ

Như vậy số các bộ hay số các bộ cần tìm bằng

Bài toán 2. Với và tập gồm phần tử, tính số tất cả các bộ các tập con có thứ tự sao cho với .

Đặt

Đặt
với .

Theo PIE:

(trong đó quy ­ước khi thì coi )

Tính được ,

Tổng quát .

Như­ vậy số cần tìm là

(To be continued)

Advertisements
Categories: Combinatorics Tags: