Matematyka.pl

Wyznaczyć wartości sum:
i) \(\displaystyle{ \sum | A \cup B |}\)
ii) \(\displaystyle{ \sum | A \cap B |}\)
iii) \(\displaystyle{ \sum | A \div B | }\)
sumy po wszystkich podzbiorach \(\displaystyle{ A, B }\) zbioru \(\displaystyle{ \{ 1,..., n \}}\).

\(\displaystyle{ \sum_{}^{} \left| A \cup B\right| }\)

Zobaczmy to na zbiorze jednoelementowym:\(\displaystyle{ \left\{ 1\right\} }\)

\(\displaystyle{ \emptyset+\left\{ 1\right\} }\)

\(\displaystyle{ \left\{ 1\right\} +\emptyset}\)

\(\displaystyle{ \left\{ 1\right\} +\left\{ 1\right\} }\)


Sumę dwóch pustych pomijamy, w ogólnym przypadku tych sum będzie:

\(\displaystyle{ \left( 2^n\right)^2-1 }\)

Nas interesuje ile jest sum , które wynoszą: \(\displaystyle{ 1,2,3,...,n}\) dla zbioru \(\displaystyle{ n}\) elementowego

Te sumy potem zliczamy...

zapiszmy:

\(\displaystyle{ b(n,k)}\) - ilość sum na zbiorze \(\displaystyle{ n}\) elementowym , które wynoszą \(\displaystyle{ k}\)

Jak widać:

\(\displaystyle{ b(1,1)=3}\)

z obserwacji:

\(\displaystyle{ b(n,1)= {n \choose 1} \cdot 3}\)

\(\displaystyle{ b(2,2)=\left( 2^2\right)^2-1-b(2,1)=15-2 \cdot 3=9 }\)

Można uogólnić:

\(\displaystyle{ b(n,n)= \left( 2^n\right)^2-1-b(n,n-1)-b(n,n-2)-...-b(n,1)}\)

Łatwo też zauważyć, że:

\(\displaystyle{ b(n,k)= {n \choose k} \cdot b(n-1,k), n>k}\)

Rekurencja jest pełna a liczenie już konkretnej sumy z zadania sprowadza się do:

\(\displaystyle{ \sum_{}^{} \left| A \cup B\right|=b(n,n) \cdot n+b(n,n-1) \cdot (n-1)+...+b(n,1) \cdot 1}\)

Pokażę to dla \(\displaystyle{ n=2}\)

\(\displaystyle{ \left\{ 1,2\right\} }\)

Sumy, których moc wynosi \(\displaystyle{ 1}\)

\(\displaystyle{ \emptyset+\left\{ 1\right\} }\)

\(\displaystyle{ \left\{ 1\right\}+\emptyset }\)

\(\displaystyle{ \left\{ 1\right\} +\left\{ 1\right\} }\)

\(\displaystyle{ \emptyset+\left\{ 2\right\} }\)

\(\displaystyle{ \left\{ 2\right\}+\emptyset }\)

\(\displaystyle{ \left\{ 2\right\} +\left\{ 2\right\} }\)

Zastosujmy wzór:

\(\displaystyle{ b(2,1)= {2 \choose 1} \cdot 3=6 }\)

Teraz sumy , które wynoszą dwa:

\(\displaystyle{ \emptyset+\left\{ 1,2\right\} }\)

\(\displaystyle{ \left\{ 1,2\right\}+\emptyset }\)

\(\displaystyle{ \left\{ 1\right\}+ \left\{ 1,2\right\} }\)

\(\displaystyle{ \left\{ 1,2\right\}+\left\{ 1\right\} }\)

\(\displaystyle{ \left\{ 2\right\}+ \left\{ 1,2\right\} }\)

\(\displaystyle{ \left\{ 1,2\right\}+\left\{ 2\right\} }\)

\(\displaystyle{ \left\{ 1,2\right\}+ \left\{ 1,2\right\} }\)

\(\displaystyle{ \left\{ 1\right\}+\left\{ 2\right\} }\)

\(\displaystyle{ \left\{ 2\right\}+\left\{ 1\right\} }\)

A ze wzoru:

\(\displaystyle{ b(2,2)=\left( 2^2\right)^2-1-b(2,1)=15-6=9}\)

Czyli się zgadza...

Czy można to "zwinąć" ?

Dobre pytanie ale na razie tego nie widzę...

Poniższe rozwiązanie podał mi ChatGPT.

ChatGPT pisze:Niech \(\displaystyle{ [n] = \{ 1, \ldots, n \}}\) i \(\displaystyle{ \chi_S(k) = \begin{cases} 0 & \text{jeśli } k \notin S, \\ 1 & \text{jeśli } k \in S. \end{cases}}\)

\(\displaystyle{ \sum_{A, B \subseteq [n]} |A \cup B| = \sum_{A, B \subseteq [n]} \sum_{k=1}^n \chi_{A \cup B}(k) = \sum_{k=1}^n \sum_{A, B \subseteq [n]} \chi_{A \cup B}(k) = \sum_{k=1}^n 3 \cdot 4^{n-1} = 3n \cdot 4^{n-1}}\).

Trzecia równość wynika z liczenia par zbiorów \(\displaystyle{ A, B \subseteq [n]}\), takich że \(\displaystyle{ k \in A \cup B}\) dla ustalonego \(\displaystyle{ k \in [n]}\). Takie pary można konstruować niezależnie decydując dla każdego \(\displaystyle{ j \in [n]}\), czy \(\displaystyle{ j \in A}\) oraz czy \(\displaystyle{ j \in B}\). Dla \(\displaystyle{ j \neq k}\) każda z czterech opcji jest możliwa, a dla \(\displaystyle{ j = k}\) odpada tylko \(\displaystyle{ j \notin A \wedge j \notin B}\). Stąd takich par jest \(\displaystyle{ 3 \cdot 4^{n-1}}\).

AI próbowało też komentować poprzednie rozwiązanie (chociaż nawet o to nie pytałem), ale tego komentarza nie wklejam, by nie sprawiać nikomu przykrości. Przed nami długa droga, by nauczyć te roboty odpowiedniej kultury i dyplomacji.

A widzisz gdzieś błąd w moim wzorze jak tak to wskaż chętnie zobaczę...