Home > Combinatorics > Số bộ các tập con

Số bộ các tập con


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)

Categories: Combinatorics Tags:
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: