Tính số cặp các tập con của tập $n$ phần tử sao cho mỗi cặp có giao khác rỗng.
Số cặp các tập con có giao khác rỗng
#1
Đã gửi 19-08-2015 - 14:07
#2
Đã gửi 19-08-2015 - 14:42
Cho mình hỏi vai trò của của các cặp là thế nào? Ý là cặp $(A,B)$ và $(B,A)$ có được tính làm một không, rỗng giao rỗng là rỗng không?
Bài viết đã được chỉnh sửa nội dung bởi Bui Ba Anh: 19-08-2015 - 14:44
#3
Đã gửi 19-08-2015 - 14:44
Cho mình hỏi vai trò của của các cặp là thế nào? Ý là cặp $(A,B)$ và $(B,A)$ có được tính làm một không, rỗng giao rỗng là rỗng không?
Dạ không.
Quyết tâm off dài dài cày hình, số, tổ, rời rạc.
#4
Đã gửi 19-08-2015 - 15:01
Tính số cặp các tập con của tập $n$ phần tử sao cho mỗi cặp có giao khác rỗng.
Gọi $A$ là số cặp tập con của tập $n$ phần tử
$B$ là số cặp tập con của $n$ phần tử mà mỗi cặp giao nhau bằng rỗng
$C$ là số cặp tập con của $n$ phần tử mà mỗi cặp giao nhau khác rỗng
Theo công thức bù trừ, ta có: $|A|=|B\bigcup C|=|B|+|C|-|B\bigcap C|=|B|+|C|$(vì không thể có cặp nào vừa giao bằng rỗng, vừa giao khác rỗng)
Dễ thấy $|A|=4^n$
Giả sử mỗi cặp thuộc $B$ có dạng $(X,Y)$ với $X,Y$ là các tập con tập $A$, giao khác rỗng, ta đi đếm số cặp này
Giả sử $X$ là một tập có $k$ phần tử, ta có $C_{n}^{k}$ cách chọn $X$
Khi đó $Y$ sẽ là một tập con của tập $n-k$ phần tử còn lại, tức là có $2^{n-k}$ cách chọn
Vậy số phần tử của $B$ là $\sum_{k=0}^{n}C^k_{n}.2^{n-k}=3^n$ (công thức khai triển Newton)
Vậy $|C|=4^n-3^n$
p/s: không chắc với kết quả, đã thử đúng với $n=1,2$
- dogsteven yêu thích
#5
Đã gửi 19-08-2015 - 15:05
Gọi $A$ là số cặp tập con của tập $n$ phần tử
$B$ là số cặp tập con của $n$ phần tử mà mỗi cặp giao nhau bằng rỗng
$C$ là số cặp tập con của $n$ phần tử mà mỗi cặp giao nhau khác rỗng
Theo công thức bù trừ, ta có: $|A|=|B\bigcup C|=|B|+|C|-|B\bigcap C|=|B|+|C|$(vì không thể có cặp nào vừa giao bằng rỗng, vừa giao khác rỗng)
Dễ thấy $|A|=4^n$
Giả sử mỗi cặp thuộc $B$ có dạng $(X,Y)$ với $X,Y$ là các tập con tập $A$, giao khác rỗng, ta đi đếm số cặp này
Giả sử $X$ là một tập có $k$ phần tử, ta có $C_{n}^{k}$ cách chọn $X$
Khi đó $Y$ sẽ là một tập con của tập $n-k$ phần tử còn lại, tức là có $2^{n-k}$ cách chọn
Vậy số phần tử của $B$ là $\sum_{k=0}^{n}C^k_{n}.2^{n-k}=3^n$ (công thức khai triển Newton)
Vậy $|C|=4^n-3^n$
p/s: không chắc với kết quả, đã thử đúng với $n=1,2$
Với $n=2$ có tập $\{1,2\}$, con của nó là $\phi, \{1\}, \{2\}, \{1,2\}$
Tông cộng có $2$ cặp tập con có giao khác giỗng, thay vào công thức của anh thì không đúng.
Bài viết đã được chỉnh sửa nội dung bởi dogsteven: 19-08-2015 - 15:05
Quyết tâm off dài dài cày hình, số, tổ, rời rạc.
#7
Đã gửi 19-08-2015 - 15:16
Các cặp đó là $(1,1),(1,12),(2,2),(2,12),(12,1),(12,2),(12,12)$ đúng $7$ cặp như đáp số nhé!
À chết, em ghi lộn đề, các cặp tập hợp nói tới đây là chỉ hai tập khác nhau.
Quyết tâm off dài dài cày hình, số, tổ, rời rạc.
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh