Problem z wybiorem podzbiorów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
pingwindyktator
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 18 mar 2014, o 23:58
Płeć: Mężczyzna
Lokalizacja: Kraków (UJ)
Podziękował: 6 razy

Problem z wybiorem podzbiorów

Post autor: pingwindyktator »

Ile jest par postaci \(\displaystyle{ \left( A, B \right)}\), gdzie \(\displaystyle{ A \subseteq B \subseteq X}\) dla \(\displaystyle{ |X| = n}\)?

Moje rozumowanie jest następujące: wybieramy podzbiór \(\displaystyle{ B}\) zbioru \(\displaystyle{ X}\) o mocy \(\displaystyle{ i}\), następnie podzbiór \(\displaystyle{ A}\) zbioru \(\displaystyle{ B}\) o mocy \(\displaystyle{ j}\). Nie zapominając o zbiorach pustych.
Zatem nasz wynik to \(\displaystyle{ \sum_{i=0}^{n} \left( {n\choose i} \cdot \sum_{j=0}^{i} {i\choose j} \right) = \sum_{i = 0}^{n} \left( {n\choose i} \cdot 2 ^{i} \right)}\)
Dobrze myślę? I czy można coś z tym wyrażeniem jeszcze zrobić?
Ostatnio zmieniony 8 mar 2015, o 23:42 przez , łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Awatar użytkownika
jutrvy
Użytkownik
Użytkownik
Posty: 1202
Rejestracja: 24 lis 2014, o 18:04
Płeć: Mężczyzna
Podziękował: 10 razy
Pomógł: 239 razy

Problem z wybiorem podzbiorów

Post autor: jutrvy »

Tak - po prostu: wybierasz na \(\displaystyle{ {n \choose i}}\) podzbiór \(\displaystyle{ i}\)-elementowy, a moc jego zbioru potęgowego wynosi \(\displaystyle{ 2^i}\). Wszystko spoko

-- 9 mar 2015, o 00:41 --

Można, przecież

\(\displaystyle{ \sum_{i=0}^n {n \choose i} 2^i = \sum_{i=0}^n {n \choose i} 2^i\cdot 1^{n-i} = 3^n}\)

Pozdro zioom

-- 9 mar 2015, o 00:42 --

Pytanie z gatunku tych extra: potrafisz dziada jakoś uogólnić? o_O
pingwindyktator
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 18 mar 2014, o 23:58
Płeć: Mężczyzna
Lokalizacja: Kraków (UJ)
Podziękował: 6 razy

Problem z wybiorem podzbiorów

Post autor: pingwindyktator »

Chodzi o wybranie \(\displaystyle{ k}\) takich zbiorów? Na pewno można to łatwo zrobić za pomocą tych sum..
ODPOWIEDZ