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

[dogsteven]

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.

[Bui Ba Anh]

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

[dogsteven]

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.

[Bui Ba Anh]

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]

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

[Bui Ba Anh]

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é!

[dogsteven]

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.