\(\displaystyle{ \sum_{A, B \subseteq X} |A \cap B|}\), gdzie \(\displaystyle{ |X| = n}\)
Wydaje mi się, że to jest:
\(\displaystyle{ \sum_{k=0}^{n} k {n\choose k} \sum_{i=0, j=0}^{n-k} {n-k\choose i} {n-k -i\choose j}}\)
Wybieramy k elementów wspólnych elementów, potem z n-k elementów wybieramy i elementow zbioru A i z n-k-i wybieramy j elementów zbioru B. moc każdego \(\displaystyle{ |A \cap B|}\) wynosi k.
Pytanie, czy to dobrze oraz jak to wysumować. Próbowałem tą sumę po i,j rozdzielić na dwie i ale potrafię pozbyć się tylko jednej sumy.
oblicz sumę, moc przecięcia zbiorów
-
- Użytkownik
- Posty: 111
- Rejestracja: 14 paź 2010, o 16:58
- Płeć: Mężczyzna
- Lokalizacja: Lublin / Warszawa
- Podziękował: 1 raz
- Pomógł: 1 raz
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
oblicz sumę, moc przecięcia zbiorów
Ja do zadania podszedłbym tak:
Niech \(\displaystyle{ X=\{1,2,\ldots , n\}}\). Zastanówmy się ile razy w zbiorach postaci \(\displaystyle{ A \cap B}\) pojawi się jedynka. Zbiór \(\displaystyle{ A}\) musi być postaci \(\displaystyle{ A=\{1\} \cup A'}\), a zbiór \(\displaystyle{ B}\) postaci \(\displaystyle{ B=\{1\} \cup B'}\), gdzie \(\displaystyle{ 1\notin A', B'}\). Zbiory \(\displaystyle{ A',B'}\) można wybrać na \(\displaystyle{ 2^{n-1}\cdot 2^{n-1}=4^{n-1}}\) sposobów (dlaczego?), zatem tyle razy pojawi się jedynka. Dokładnie tyle samo razy pojawi się każda z pozostałych \(\displaystyle{ n}\) liczb, dlatego szukana suma to \(\displaystyle{ n\cdot 4^{n-1}}\).
Q.
Niech \(\displaystyle{ X=\{1,2,\ldots , n\}}\). Zastanówmy się ile razy w zbiorach postaci \(\displaystyle{ A \cap B}\) pojawi się jedynka. Zbiór \(\displaystyle{ A}\) musi być postaci \(\displaystyle{ A=\{1\} \cup A'}\), a zbiór \(\displaystyle{ B}\) postaci \(\displaystyle{ B=\{1\} \cup B'}\), gdzie \(\displaystyle{ 1\notin A', B'}\). Zbiory \(\displaystyle{ A',B'}\) można wybrać na \(\displaystyle{ 2^{n-1}\cdot 2^{n-1}=4^{n-1}}\) sposobów (dlaczego?), zatem tyle razy pojawi się jedynka. Dokładnie tyle samo razy pojawi się każda z pozostałych \(\displaystyle{ n}\) liczb, dlatego szukana suma to \(\displaystyle{ n\cdot 4^{n-1}}\).
Q.
-
- Użytkownik
- Posty: 111
- Rejestracja: 14 paź 2010, o 16:58
- Płeć: Mężczyzna
- Lokalizacja: Lublin / Warszawa
- Podziękował: 1 raz
- Pomógł: 1 raz
oblicz sumę, moc przecięcia zbiorów
Interesuje nas liczność zbiorów, stąd jest ta potęga. Mam rację?