Topic về các bài toán: Tập hợp - Logic tập hợp
#1
Đã gửi 14-11-2012 - 22:04
Problem 1: Có bao nhiêu cặp tập con không giao nhau của một tập hợp $X$ gồm $n$ phần tử.
- perfectstrong, funcalys, minhtuyb và 2 người khác yêu thích
#2
Đã gửi 14-11-2012 - 22:08
-Xét $A,B$ là hai tập con thỏa mãn đề bài.Có gì thắc mắc mọi người có thể thắc mắc ngay trong topic này, đề bài nhớ ghi rõ nguồn nếu biết, mong mọi người ủng hộ. Bây giờ ta vào vấn đề chính nào:
Problem 1: Có bao nhiêu cặp tập con không giao nhau của một tập hợp $X$ gồm $n$ phần tử.
-Với mỗi phần tử trong tập hợp $X$, có 3 khả năng xảy ra:
+) $x\in A;x\not\in B$
+) $x\in B;x\not\in A$
+) $x\not\in A;x\not\in B$
Vì tập $X$ có $n$ phần tử $\Rightarrow $ có $3^n$ trạng thái $\Rightarrow$ có tổng cộng $3^n$ cặp tập con thỏa mãn đề bài.
-------------------------------------------------------------
Đây là topic thảo luận, không cần xoá đâu em!
Bài viết đã được chỉnh sửa nội dung bởi Trần Đức Anh @@: 14-11-2012 - 22:20
#4
Đã gửi 14-11-2012 - 22:20
Problem 2: Cho tập hợp $X$ gồm $n$ phần tử. Với mỗi cặp tập con $A_{1}$, $A_{2}$ của $X$ ta tính được số phần tử của $A_{1}\cap{A_{2}}$. Chứng minh rằng tất cả các số nhận được bằng $n4^{n-1}$
#5
Đã gửi 14-11-2012 - 22:32
Em quên đếm số tập bị lặp :-Xét $A,B$ là hai tập con thỏa mãn đề bài.
-Với mỗi phần tử trong tập hợp $X$, có 3 khả năng xảy ra:
+) $x\in A;x\not\in B$
+) $x\in B;x\not\in A$
+) $x\not\in A;x\not\in B$
Vì tập $X$ có $n$ phần tử $\Rightarrow $ có $3^n$ trạng thái $\Rightarrow$ có tổng cộng $3^n$ cặp tập con thỏa mãn đề bài.
-------------------------------------------------------------
Đây là topic thảo luận, không cần xoá đâu em!
----
Bổ sung: Trong $3^n$ cặp tập con đó có một cặp $(\varnothing
;\varnothing)$ và các cặp còn lại, mỗi cặp được đếm 2 lần nên số tập con thỏa mãn là: $\dfrac{3^n-1}{2}+1=\dfrac{3^n+1}{2}$
Bài viết đã được chỉnh sửa nội dung bởi minhtuyb: 14-11-2012 - 23:03
- Trần Đức Anh @@ yêu thích
#6
Đã gửi 14-11-2012 - 22:49
Có tất cả $4^n$ cặp tập con $(A,B)$ của XChúng ta tiếp tục với bài toán sau:
Problem 2: Cho tập hợp $X$ gồm $n$ phần tử. Với mỗi cặp tập con $A_{1}$, $A_{2}$ của $X$ ta tính được số phần tử của $A_{1}\cap{A_{2}}$. Chứng minh rằng tất cả các số nhận được bằng $n4^{n-1}$
Ta chia các tập con này thành các bộ $4$: $(A \cap B,\bar{A} \cap B,A \cap \bar{B},\bar{A}\cap \bar{B})$, có $4^{n-1}$ bộ như vậy
Khi đó mỗi phần tử $a\in X$ chỉ thuộc 1 trong trong 4 cặp thuộc 1 bộ mà có n phần tử
$\Rightarrow \sum A\cap B= n.4^{n-1}$
Bài viết đã được chỉnh sửa nội dung bởi soros_fighter: 14-11-2012 - 22:51
- perfectstrong và Trần Đức Anh @@ thích
#7
Đã gửi 14-11-2012 - 23:09
- Trần Đức Anh @@ yêu thích
#9
Đã gửi 15-11-2012 - 21:47
- funcalys yêu thích
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh