szukanie zaawansowane
 [ Posty: 12 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 13 cze 2015, o 21:35 
Użytkownik
Avatar użytkownika

Posty: 86
Lokalizacja: Wrocław
Zadanie 1: Jaka jest moc zbioru \left\{ \left( A,B,C\right)\in P\left( \left[ n\right] \right)  ^{3} : A = B \cap C  \right\}
\left[ n\right] = \left\{ 1, ..., n\right\}

D = \left\{ \left( A,B,C\right)\in P\left( \left[ n\right] \right)  \times  P\left( \left[ n\right] \right) \times   P\left( \left[ n\right] \right) : A = B \cap C  \right\}
Zbiór A zalezy od zbiorow B i C wiec prawda jest:
\left| D\right| =  \left\{ \left( B,C\right)\in P\left( \left[ n\right] \right)  \times  P\left( \left[ n\right] \right)  \right\} = 2 ^{n}  \cdot 2 ^{n} = 4 ^{n}

Czy moje rozwiązanie jest poprawne?

Zadanie 2: Podaj zwartą postać sumy:
\sum_{k=0}^{n}k ^{2} {n \choose k} = \sum_{k=1}^{n}k ^{2}  \frac{n}{k} {n-1 \choose k-1}=n \sum_{k=1}^{n}k {n-1 \choose k-1}=n \sum_{k=1}^{n}k  \frac{n-1}{k-1}  {n-2 \choose k-2} = n(n-1) \sum_{k=1}^{n}  \frac{k}{k-1}  {n-2 \choose k-2}
Dalej niestety nie wiem jak to pociągnąć..
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Kobieta Offline
PostNapisane: 13 cze 2015, o 22:01 
Użytkownik
Avatar użytkownika

Posty: 2505
Ad 1: wyobraź sobie, że zbioru A nie ma, wtedy zliczasz B, C \subseteq \{1, \dots, n\}.

Ad 2: skreśl wszystko, to nie jest właściwa droga do celu. Myśl kom-bi-na-to-rycz-nie. Z n osób wybierasz k i... i co dalej? Podpowiem, że odpowiedź to 2^{n-2} n (n+1).
Góra
Mężczyzna Offline
PostNapisane: 13 cze 2015, o 22:02 
Użytkownik
Avatar użytkownika

Posty: 86
Lokalizacja: Wrocław
Napisałem właśnie wyżej coś takiego. Czy to jest dobrze?
Góra
Kobieta Offline
PostNapisane: 13 cze 2015, o 22:07 
Użytkownik
Avatar użytkownika

Posty: 2505
Może i dobrze (jak teraz patrzę), ale z formalnego punktu widzenia... myślę, że chociażby Jan Kraszewski będzie miał Ci coś do powiedzenia.
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 19:10 
Użytkownik
Avatar użytkownika

Posty: 86
Lokalizacja: Wrocław
\sum_{k=0}^{n}k ^{2} {n \choose k}
Nie mam pomysłu jak to rozpisać ten kwadrat wszystko komplikuje, ani z wzoru Newtona nie jestem w stanie, ani w taki sposób jak próbowałem wyżej.
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 19:23 
Użytkownik
Avatar użytkownika

Posty: 11816
Lokalizacja: Wrocław
k^{2}=k(k-1+1)=k(k-1)+k i można rozbić na dwie sumy, które liczy się np. tak:
ze wzoru dwumianowego Newtona mamy (x+1)^{n}= \sum_{k=0}^{n}{n \choose k}x^{k}. Różniczkując tę tożsamość stronami raz, mamy n(x+1)^{n-1}= \sum_{k=1}^{n}{n \choose k}kx^{k-1}. Natomiast różniczkując drugi raz, dostajemy n(n-1)(x+1)^{n-2}= \sum_{k=2}^{n}{n \choose k}k(k-1)x^{k-2}
Podstawiamy teraz x=1. No i trzeba uważać na zerowy i pierwszy wyraz.

Była też jakaś ładna interpretacja kombinatoryczna, której nie pamiętam, a wymyślić nie potrafię.
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 19:55 
Użytkownik
Avatar użytkownika

Posty: 86
Lokalizacja: Wrocław
W takim wypadku mamy na początku:
\sum_{k=0}^{n}\left( k\left( k-1\right) + k\right) {n \choose k} = \sum_{k=0}^{n}k {n \choose k} + \sum_{k=0}^{n} k\left(k-1 \right)  {n \choose k}
Wynik pierwszej sumy to n \cdot  2^{n-1}
Drugiej sumy n\left( n-1\right)2 ^{n-2} (Rozwiązałem to w taki sposób jak na początku próbowałem, ale teraz wszystko ładnie się skróciło)
Ostatecznie: n \cdot  2^{n-1} + n\left( n-1\right)2 ^{n-2}
Po doprowadzeniu do ostatecznej postaci mamy:
Medea 2 napisał(a):
Podpowiem, że odpowiedź to 2^{n-2} n (n+1)


Nigdzie się nie pomyliłem?
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2015, o 20:09 
Użytkownik
Avatar użytkownika

Posty: 11816
Lokalizacja: Wrocław
Jest w porządku.
Góra
Kobieta Offline
PostNapisane: 14 cze 2015, o 20:13 
Użytkownik
Avatar użytkownika

Posty: 2505
Nie, Twoją sumę można zwinąć do mojej przez n \cdot 2^{n-1} = 2 \cdot 2^{n-2}. To teraz obiecana interpretacja kombinatoryczna.

Po lewej wybierasz z n osób k-osobową grupę i dajesz im dwa cukierki (jeden pomarańczowy, drugi limonkowy, może tej samej osobie, może nie). Po prawej zaś (2^{n-2} n (n+1) rozbite tak, jak u Ciebie) możesz wybrać jedną osobę (z dwoma cukierkami) i dowolny podzbiór z pozostałych n-1 (oni, razem z cukierkową, będą tworzyć k-grupę) lub dwie osoby (każda ze swoim cukierkiem) i dowolny podzbiór z pozostałych n-2 osób.
Góra
Mężczyzna Offline
PostNapisane: 15 cze 2015, o 15:31 
Użytkownik
Avatar użytkownika

Posty: 86
Lokalizacja: Wrocław
Wracając do zadania 1, intersuję mnie teraz poprawny zapis rozumowania w tym zadaniu.
Zadanie 1: Jaka jest moc zbioru \left\{ \left( A,B,C\right)\in P\left( \left[ n\right] \right) ^{3} : A = B \cap C \right\}

Niech:
D = \left\{ \left( A,B,C\right)\in P\left( \left[ n\right] \right) ^{3} : A = B \cap C \right\}
E = \left\{ \left( B,C\right)\in P\left( \left[ n\right] \right) ^{2}\right\}

\left| E\right|=\left|  \left\{ B \in P([n])\right\} \times \left\{ C \in P([n])\right\}\right|

(W tym momencie nie jestem pewien czy nie powiniem to przejście jakoś zaargumentować)

\left| E\right|=2 ^{n} \cdot 2 ^{n} = 4 ^{n}

Zauważmy, że \left| D\right| = \left| E\right|, ponieważ w rodzinie zbiorów D zbiór A całkowicie zależy od B,C, więc nie generuje żadnych nowych kombinacji. Stąd:
\left| D\right| = 4 ^{n}

Czy coś takiego jest akceptowalne?
Góra
Kobieta Offline
PostNapisane: 15 cze 2015, o 17:04 
Użytkownik
Avatar użytkownika

Posty: 2505
To przejście znane jest jako twierdzenie o mnożeniu (z kombinatoryki). Równość |D| = |E| uzasadniłabym wskazując bijekcję D \to E, (A, B, C) \mapsto (B, C).
Góra
Mężczyzna Offline
PostNapisane: 15 cze 2015, o 19:26 
Użytkownik
Avatar użytkownika

Posty: 86
Lokalizacja: Wrocław
Co do przejścia |D| = |E| trzeba napisać ze na podstawie twierdzenia o mnożeniu albo coś w stylu ze zbiory są parami rozłączne i dopiero do kroku z zwykłym mnożeniem czy poprostu bez wspominania o tym?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 12 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Jaka jest moc zbioru  silvaran  4
 Jaka jest moc zbioru - zadanie 2  Hory314  28
 Jaka jest moc zbioru - zadanie 3  posciel  21
 Jaka jest moc zbioru - zadanie 4  addmir  36
 Jaka jest moc zbioru - zadanie 5  macmac664  8
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl