oblicz sumę, moc przecięcia zbiorów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Heniek1991
Użytkownik
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

Post autor: Heniek1991 » 9 sie 2011, o 19:00

\(\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.

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

oblicz sumę, moc przecięcia zbiorów

Post autor: » 9 sie 2011, o 19:42

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.

Heniek1991
Użytkownik
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

Post autor: Heniek1991 » 9 sie 2011, o 19:54

Interesuje nas liczność zbiorów, stąd jest ta potęga. Mam rację?

ODPOWIEDZ