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

[phathuy]

 Giả sử ${{F}_{k}}$ là tập hợp tất cả các bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ trong đó ${{A}_{i}}\left( i=\overline{1,k} \right)$ là một tập con của ${{X}_{n}}=\left\{ 1,2,...,n \right\}$. Biết rằng các tập ${{A}_{1}},{{A}_{2}},...,{{A}_{k}}$có thể trùng nhau. Hãy tính \[{{S}_{n}}=\sum\limits_{\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)\in {{F}_{k}}}{\left| \bigcup\limits_{i=1}^{k}{{{A}_{i}}} \right|}\].

Trong một tài liệu có lời giải sau: (mình chép lại nguyên xi)

Do có ${{2}^{n}}$ tập con của ${{X}_{n}}$ nên có ${{2}^{nk}}$ bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$. Với mỗi bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n-1}}$ ta có thể thêm hoặc không thêm n vào tập ${{A}_{i}}$ để được bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n}}$. Với chú ý rằng số bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n-1}}$ là ${{2}^{\left( n-1 \right)k}}$ và có ${{2}^{k}}-1$ cách thêm n vào bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n-1}}$ thì ta có ${{S}_{n}}={{2}^{k}}{{S}_{n-1}}+\left( {{2}^{k}}-1 \right){{2}^{k\left( n-1 \right)}}$.

Dễ thấy ${{S}_{1}}={{2}^{k}}-1$. Từ đấy bằng quy nạp ta chứng minh được ${{S}_{n}}=n{{.2}^{k\left( n-1 \right)}}\left( {{2}^{k}}-1 \right)$.

Mình không hiểu chỗ bôi đỏ? Các bạn giải thích giúp mình nha.

[HeilHitler]

 Giả sử ${{F}_{k}}$ là tập hợp tất cả các bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ trong đó ${{A}_{i}}\left( i=\overline{1,k} \right)$ là một tập con của ${{X}_{n}}=\left\{ 1,2,...,n \right\}$. Biết rằng các tập ${{A}_{1}},{{A}_{2}},...,{{A}_{k}}$có thể trùng nhau. Hãy tính \[{{S}_{n}}=\sum\limits_{\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)\in {{F}_{k}}}{\left| \bigcup\limits_{i=1}^{k}{{{A}_{i}}} \right|}\].

Trong một tài liệu có lời giải sau: (mình chép lại nguyên xi)

Do có ${{2}^{n}}$ tập con của ${{X}_{n}}$ nên có ${{2}^{nk}}$ bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$. Với mỗi bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n-1}}$ ta có thể thêm hoặc không thêm n vào tập ${{A}_{i}}$ để được bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n}}$. Với chú ý rằng số bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n-1}}$ là ${{2}^{\left( n-1 \right)k}}$ và có ${{2}^{k}}-1$ cách thêm n vào bộ $\left( {{A}_{1}},{{A}_{2}},...,{{A}_{k}} \right)$ của ${{X}_{n-1}}$ thì ta có ${{S}_{n}}={{2}^{k}}{{S}_{n-1}}+\left( {{2}^{k}}-1 \right){{2}^{k\left( n-1 \right)}}$.

Dễ thấy ${{S}_{1}}={{2}^{k}}-1$. Từ đấy bằng quy nạp ta chứng minh được ${{S}_{n}}=n{{.2}^{k\left( n-1 \right)}}\left( {{2}^{k}}-1 \right)$.

Mình không hiểu chỗ bôi đỏ? Các bạn giải thích giúp mình nha.

Với mỗi bộ $(A_1,A_2,...,A_k)$ của $X_{n-1}$, sẽ có $2^k-1$ cách thêm $n$ vào nó để trở thành một bộ của $X_{n}$. Mỗi cách thêm này sẽ làm số phần tử của $\bigcup_{i=1}^{k} A_i$ tăng $1$ nên với mỗi bộ $(A_1,A_2,...,A_k)$ của $X_{n-1}$ ban đầu, các cách thêm $n$ làm tổng số phần tử tăng thêm $2^{k}-1$. Do có $2^{k(n-1)}$ bộ $(A_1,A_2,...,A_k)$ của $X_{n-1}$ nên tổng  số phần tử $S_{n-1}$sẽ tăng lên $(2^k-1)2^{k(n-1)}$ sau phép bổ sung phần tử $n$. (1)

Với mỗi bộ $(A_1,A_2,...,A_k)$ của $X_{n-1}$ ban đầu, một cách thêm $n$ vào nó sẽ tạo ra một bộ $(A_1,A_2,...,A_k)$ mới của $X_n$. Do có $2^k-1$ cách thêm $n$ vào bộ này nên số bộ mới tạo ra của $X_n$ sẽ là $2^k-1$ bộ, tính cả bản thân bộ $(A_1,A_2,...,A_k)$ của $X_{n-1}$ ban đầu là thành $2^k$ bộ. Như vậy số phần tử của bộ $(A_1,A_2,...,A_k)$ của $X_{n-1}$ sẽ được tính lặp $2^k$ lần. (2)
Từ (1) và (2) rút ra hệ thức màu đỏ.