Dany jest \(\displaystyle{ n}\)-elementowy zbiór \(\displaystyle{ X}\), przy czym \(\displaystyle{ n>0}\). Wykaż, że
\(\displaystyle{ \sum_{A,B \subseteq X}^{}\left| A \cup B\right|=3n \cdot 4^{n-1}}\).
Jak to zrobić? Jakaś wskazówka?
Dany jest n-elementowy zbiór
-
Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Dany jest n-elementowy zbiór
Można też kombinatorycznie: trójkę \(\displaystyle{ (A, B, x)}\) - gdzie \(\displaystyle{ A, B \subseteq X}\) i \(\displaystyle{ x \in X}\) - nazwiemy kolorową, jeśli \(\displaystyle{ x \in A \cup B}\). Wtedy lewa strona równości to liczba kolorowych trójek, co dobrze widać, jeśli dla ustalonych \(\displaystyle{ A^*, B^* \subseteq X}\), zliczymy wszystkie kolorowe trójki postaci \(\displaystyle{ (A^*, B^*, x)}\).
Z drugiej strony kolorowe trójki można zliczyć odwrotnie - przy ustalonym \(\displaystyle{ x^* \in X}\) zliczyć trójki postaci \(\displaystyle{ (A, B, x^*)}\). Aby to zrobić, dla każdego elementu \(\displaystyle{ x \in X \setminus \{ x^* \}}\) dowolnie wybieramy jedną z czterech możliwości: \(\displaystyle{ x \in A \cap B, x \in A \setminus B, x \in B \setminus A}\) lub \(\displaystyle{ x \notin A \cup B}\). Natomiast dla \(\displaystyle{ x^*}\) odpada ostatnia możliwość, wszak żądamy by \(\displaystyle{ x^* \in A \cup B}\). Par \(\displaystyle{ (A, B)}\) tworzących z ustalonym \(\displaystyle{ x^*}\) kolorową trójkę jest więc \(\displaystyle{ 3 \cdot 4^{n-1}}\). Ponieważ zaś możliwości na \(\displaystyle{ x^*}\) jest \(\displaystyle{ n}\), ostatecznie dostajemy wzór na liczbę kolorowych trójek: \(\displaystyle{ 3n \cdot 4^{n-1}}\), czyli to co po prawej stronie.
Z drugiej strony kolorowe trójki można zliczyć odwrotnie - przy ustalonym \(\displaystyle{ x^* \in X}\) zliczyć trójki postaci \(\displaystyle{ (A, B, x^*)}\). Aby to zrobić, dla każdego elementu \(\displaystyle{ x \in X \setminus \{ x^* \}}\) dowolnie wybieramy jedną z czterech możliwości: \(\displaystyle{ x \in A \cap B, x \in A \setminus B, x \in B \setminus A}\) lub \(\displaystyle{ x \notin A \cup B}\). Natomiast dla \(\displaystyle{ x^*}\) odpada ostatnia możliwość, wszak żądamy by \(\displaystyle{ x^* \in A \cup B}\). Par \(\displaystyle{ (A, B)}\) tworzących z ustalonym \(\displaystyle{ x^*}\) kolorową trójkę jest więc \(\displaystyle{ 3 \cdot 4^{n-1}}\). Ponieważ zaś możliwości na \(\displaystyle{ x^*}\) jest \(\displaystyle{ n}\), ostatecznie dostajemy wzór na liczbę kolorowych trójek: \(\displaystyle{ 3n \cdot 4^{n-1}}\), czyli to co po prawej stronie.