Chủ đề này có 4 trả lời

[hpeinstein]

Tìm tất cả các cặp tập con không giao nhau của tập hợp n phần tử!!!

[leecom]

Ta xét một phần tử bất kì http://dientuvietnam...n/mimetex.cgi?A là tập có n phần tử.
Xảy ra 3 khả năng:
- hoặc là http://dientuvietnam...n/mimetex.cgi?a thuộc tập thứ nhất.
- hoặc là http://dientuvietnam...n/mimetex.cgi?a thuộc tập thứ hai.
- hoặc là http://dientuvietnam...n/mimetex.cgi?a không thuộc tập nào cả.
Chú ý là với cặp http://dientuvietnam...imetex.cgi?(B,C) thì ta cũng đã xét cả cặp http://dientuvietnam...imetex.cgi?(C,B)
Do đó sẽ có http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{3^{n}}{2} cặp tập con thỏa mãn.

[manutd]

@leecom: http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{3^n}{2} không phải là số nguyên, bạn đếm nhầm rồi!
Cách của tôi như sau: Ta tiến hành đếm số cặp tập con không giao nhau của A. Xét một tập con X có http://dientuvietnam...n/mimetex.cgi?k phần tử http://dientuvietnam...metex.cgi?C_n^k cách chọn X, và có http://dientuvietnam...tex.cgi?2^{n-k} cách chọn tập Y sao cho X và Y không giao nhau. Tập Y là một tập con bất kì của tập http://dientuvietnam...mimetex.cgi?k=0 hay X là tập rỗng thì chỉ có http://dientuvietnam...metex.cgi?2^n-1 cách chọn tập Y như vậy. Chú ý, trong phép đếm này, mỗi cặp tập con thỏa mãn đã được tính 2 lần. Vậy đáp số là:

@leecom: Bạn nói rõ hơn cách của bạn được không, trông nó khá là đẹp đấy!

[detectivehien]

Ta xét một phần tử bất kì http://dientuvietnam...n/mimetex.cgi?A là tập có n phần tử.
Xảy ra 3 khả năng:
- hoặc là http://dientuvietnam...n/mimetex.cgi?a thuộc tập thứ nhất.
- hoặc là http://dientuvietnam...n/mimetex.cgi?a thuộc tập thứ hai.
- hoặc là http://dientuvietnam...n/mimetex.cgi?a không thuộc tập nào cả.
Chú ý là với cặp http://dientuvietnam...imetex.cgi?(B,C) thì ta cũng đã xét cả cặp http://dientuvietnam...imetex.cgi?(C,B)
Do đó sẽ có http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{3^{n}}{2} cặp tập con thỏa mãn.

Theo em thì bổ sung vào cái đoạn gần cuối là cặp tập con rỗng thì chỉ tính 1 lần, từ đó có đáp án như trên.

[leecom]

Ta xét một phần tử bất kì http://dientuvietnam...n/mimetex.cgi?A là tập có n phần tử.
Xảy ra 3 khả năng:
- hoặc là http://dientuvietnam...n/mimetex.cgi?a thuộc tập thứ nhất.
- hoặc là http://dientuvietnam...n/mimetex.cgi?a thuộc tập thứ hai.
- hoặc là http://dientuvietnam...n/mimetex.cgi?a không thuộc tập nào cả.
Chú ý là với cặp http://dientuvietnam...imetex.cgi?(B,C) thì ta cũng đã xét cả cặp http://dientuvietnam...imetex.cgi?(C,B)
Do đó sẽ có http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{3^{n}}{2} cặp tập con thỏa mãn.

Theo em thì bổ sung vào cái đoạn gần cuối là cặp tập con rỗng thì chỉ tính 1 lần, từ đó có đáp án như trên.

Đúng rồi đó. Mình viết thiếu. Xin lỗi nha!

Bài viết đã được chỉnh sửa nội dung bởi leecom: 17-09-2006 - 10:17