szukanie zaawansowane
 [ Posty: 14 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 7 kwi 2016, o 22:22 
Użytkownik

Posty: 47
Witam, mam problem z takim zadaniem - Na ile sposobów można utworzyć ciąg o 10 wyrazach ze zbioru \{1,2,...,123\}, tak aby dokładnie sześć jego elementów było parzystych?

Odpowiedź to: {10 \choose 6}  \cdot 61 ^{6} \cdot 62 ^{4}

61 ^{6} \cdot 62 ^{4} - ten fragment rozumiem, ale skoro tworzymy ciąg z powtórzeniami o długości 6 ze wszystkich liczb parzystych i ciąg z powtórzeniami o długości 4 ze wszystkich liczb nieparzystych, a następnie wymnażamy, to według mnie to jest już odpowiedź ostateczna. Nie rozumiem po co jeszcze kombinacje dodawać. Czy może mi ktoś to wytłumaczyć? Mile widziany by był przykład dlaczego mój sposób myślenia nie jest poprawny. Z góry dzięki.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 7 kwi 2016, o 22:44 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Bo wybierasz te miejsca z dziesięciu na których będą stały wyrazy parzyste.
Góra
Mężczyzna Offline
PostNapisane: 7 kwi 2016, o 22:47 
Użytkownik
Avatar użytkownika

Posty: 58
Lokalizacja: Kraków
Tak jak wspomniałeś, 61 ^{6} odpowiada ilości wariacji z powtórzeniami 6-elementowych ze zbioru 61-elementowego. Analogicznie 62^{4}. Natomiast zauważ, że mnożąc tylko te dwie liczby dostaniesz odpowiedź dla ciągów, gdzie np. pierwsze 6 cyfr jest parzyste, a pozostałe nieparzyste. Jak sobie to zrobisz na papierze to zauważysz, że wychodzi własnie 61 ^{6}\cdot 62 ^{4}. A co z pozostałymi ciągami, gdzie na przykład na zmiane występują cyfry parzyste i nieparzyste? {10 \choose 6} odpowiada wybraniu 6 miejsc dla liczb parzystych z 10 możliwych. Można równie dobrze wybrać 4 miejsca z dziesięciu dla nieparzystych, bo przecież
{n \choose k}={n \choose {n-k}}.
Góra
Mężczyzna Offline
PostNapisane: 7 kwi 2016, o 22:57 
Użytkownik

Posty: 47
Wszystko jasne, dziękuję za odpowiedź.

-- 7 kwi 2016, o 23:21 --

A czy byłby ktoś jeszcze tak miły i wyjaśnił, dlaczego w tym zadaniu "Na ile sposobów można utworzyć zbiór złożony z 10 elementów, które należą do zbioru \{1, 2, . . . , 123\}?" odpowiedź wynosi {123 \choose 10}, a nie korzystamy ze wzoru na wariacje z powtórzeniami, skoro w treści zadania nie jest wspomniane o zbiorze zawierającym różne elementy? Czy można to zadanie interpretować dwojako, czy ma tylko jedno poprawne rozwiązanie?
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2016, o 00:08 
Administrator

Posty: 22651
Lokalizacja: Wrocław
WhiteRabbit7 napisał(a):
skoro w treści zadania nie jest wspomniane o zbiorze zawierającym różne elementy?

Elementy w zbiorze zawsze są różne.

JK
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2016, o 01:00 
Użytkownik

Posty: 47
I wszystko jasne. To ostatnie pytanie na dzisiaj - "dla k \ge 3, ile jest ciągów k-elementowych o wyrazach ze zbioru \left\{ {1,2,3,4,5,6}\right\}, gdzie co najmniej trzy z wyrazów ciągu są równe 6 ?"

Dlaczego odpowiedź {k \choose 3} \cdot 6 ^{k-3} jest niepoprawna? Rozumuję w ten sposób, że na początku obliczam ilość możliwości umieszczenia 6 na k pozycjach, zatem {k \choose 3}, a następnie na pozostałych rozmieszczam resztę liczb łącznie z 6, ponieważ liczba 6 może wystąpić ze względu na to, że k \ge 3.
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2016, o 01:18 
Użytkownik

Posty: 146
Lokalizacja: Wrocław
Ale w tym ciągu ma być dokładnie trzy szóstki a Ty na pozostałych miejscach które Ci zostały dalej chcesz wstawiać szóstki.
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2016, o 01:24 
Użytkownik

Posty: 47
Treść zadania poprawiona, przepraszam za błąd.
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2016, o 15:03 
Użytkownik
Avatar użytkownika

Posty: 58
Lokalizacja: Kraków
WhiteRabbit7 napisał(a):
Dlaczego odpowiedź {k \choose 3} \cdot 6 ^{k-3} jest niepoprawna?
Chodzi o to, żeby co najmniej 3 wyrazy twojego ciągu były równe 6, co gwarantujesz sobie przez symbol Newtona. Następnie liczysz liczbę wariacji z powtórzeniami k-3-elementowych ze zbioru 6-elementowego, co znaczy, że także 6 mogą występować na miejscach różnych od tych trzech, które wybrałeś. Według mnie to tutaj pojawia się błąd bo jeżeli chciałbyś mieć dokładnie trzy szóstki, to twoje rozwiązanie ci tego nie gwarantuje, ponieważ nie wiesz, czy w tych wariacjach pojawi się 6, czy też nie. Według mnie do problemu należałoby podejść tradycyjnie, czyli zsumować wszystkie przypadki, gdzie szóstek będzie odpowiednio 3, 4, 5, ..., k \quad dla \quad k \ge 3. Jednakże mając na uwadze to, że już dla małego k może wyjść dużo rachunków, a co do dopiero dla dużego, to oczywiście policzymy sobie możliwości dla zdarzenia przeciwnego. Czyli mamy trzy przypadki:
I - zero szóstek;
II - jedna szóstka;
III - dwie szóstki.
Na końcu wynik oczywiście odejmujemy od wszystkich ilości naszych wariacji z powtórzeniami w tym zadaniu (bo policzyliśmy możliwości dla zdarzenia przeciwnego).

~edit
Z drugiej strony to tych rachunków praktycznie w ogóle nie będzie, bo patrzymy na ogólny przypadek dla ciągu o długości k wyrazów, także nie musimy liczyć możliwości dla zdarzenia przeciwnego, bo pojawią nam się tutaj po prostu jakieś sumy zależne od k i tyle.
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2016, o 18:36 
Użytkownik

Posty: 47
Waylays napisał(a):
WhiteRabbit7 napisał(a):
Dlaczego odpowiedź {k \choose 3} \cdot 6 ^{k-3} jest niepoprawna?
Chodzi o to, żeby co najmniej 3 wyrazy twojego ciągu były równe 6, co gwarantujesz sobie przez symbol Newtona. Następnie liczysz liczbę wariacji z powtórzeniami k-3-elementowych ze zbioru 6-elementowego, co znaczy, że także 6 mogą występować na miejscach różnych od tych trzech, które wybrałeś. Według mnie to tutaj pojawia się błąd bo jeżeli chciałbyś mieć dokładnie trzy szóstki, to twoje rozwiązanie ci tego nie gwarantuje, ponieważ nie wiesz, czy w tych wariacjach pojawi się 6, czy też nie.

Ale skoro robię wariację z powtórzeniami, to mam pewność, że zostaną wyliczone wszystkie przypadki, łącznie z tymi gdzie liczby 6 na tych k-3 miejscach nie będzie. Chciałbym się dowiedzieć gdzie leży mój błąd w myśleniu, dlatego ciągnę temat. Jak to zrozumiem, to się wezmę za liczenie zadania w inny sposób.
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2016, o 19:46 
Użytkownik
Avatar użytkownika

Posty: 58
Lokalizacja: Kraków
Okay, żeby uwidocznić błąd, który nam się wkradł, przypatrzymy się konkretnemu przypadkowi. Na przykładzie k=4 najprościej będzie pokazać. Chodzi o to, że kiedy wybierasz trzy z czterech miejsc dla szóstek, to nie powinieneś już później zakładać, że pojawią się kolejne szóstki. Teraz zauważ, że jeżeli jednak tak postąpimy, to wybieramy np. 3 pierwsze miejsca, czyli mamy \left( 6, 6, 6, x\right). Teraz uważasz, że na ostatnim możemy wstawić cokolwiek, także szóstkę. No to mamy wtedy \left( 6, 6, 6, 6\right). Teraz chcemy wybrać ostatnie trzy miejsca, czyli \left( x, 6, 6, 6\right). Jeżeli teraz postawimy szóstkę na początku, to okazuje się, że policzymy \left( 6, 6, 6, 6\right) dwa razy. Ogółem dla k=4 policzymy w ten sposób 4 razy to samo ustawienie \left( 6, 6, 6, 6\right) zamiast policzyć je raz. Więc w takich wypadkach zawsze najprościej jest trzaskać przypadki.

Czyli w tym wypadku po prostu zachodziłyby 4 możliwości ulokowania x, gdzie x mógłby być dowolną liczbą naturalną od 1 do 5 (razem 4\cdot 5=20) i jeszcze dodajemy 1, dla czterech szóstek (zamiast liczyć 4 razy takie ustawienie, liczymy raz).
I: {4 \choose 3}\cdot 5^{4-3}=4\cdot5=20
II: {4 \choose 4}\cdot 5^{4-4}=1\cdot 1=1
20+1=21
Wynik jak najbardziej prawidłowy, żeby się upewnić sprawdziłem w programie i było okay.
Góra
Mężczyzna Offline
PostNapisane: 10 kwi 2016, o 19:36 
Użytkownik

Posty: 47
Oto rozwiązanie zadania:
6 ^{n}-5 ^{n}-n \cdot 5 ^{n-1}- {n \choose 2} \cdot 5 ^{n-2}
Teraz staram się po kolei je przeanalizować, jednak chyba średnio mi idzie. Będę wdzięczny za wskazanie błędów w rozumowaniu:
6 ^{n} - obliczamy wszystkie możliwe wariacje z powtórzeniami, a następnie będziemy odejmować od nich nie interesujące nas ciągi
5 ^{n} - po odjęciu tej wariacji otrzymamy wszystkie możliwe ciągi, które zawierają na przykład liczbę 6
n \cdot 5 ^{n-1} - dzięki odjęciu tego otrzymamy liczbę ciągów, które składają się z dwóch liczb, są postaci np. dla n=4 xyyy, xxyy itd.
{n \choose 2} \cdot 5 ^{n-2} - tutaj już nie rozumiem zbytnio o co chodzi, zapewne powyższe analizy też nie są idealne, zatem będę wdzięczny za wskazanie
i wytłumaczenie błędów

-- 10 kwi 2016, o 20:49 --

I tak abstrahując od zadania, to czy jest jakaś różnica w losowaniu ze zwracaniem, a losowaniu bez zwracania, jeśli w zadaniu wybieram tylko jednorazowo za jednym zamachem pewną ilość elementów spośród wszystkich elementów?
Góra
Mężczyzna Offline
PostNapisane: 11 kwi 2016, o 02:25 
Użytkownik
Avatar użytkownika

Posty: 58
Lokalizacja: Kraków
No to jest dokładnie to, o czym pisałem. Patrzymy na zdarzenie przeciwne i mamy trzy przypadki:
I: żaden z wyrazów ciągu nie jest równy 6. Takich ciągów jest 5^n
II: dokładnie jeden wyraz ciągu jest równy 6. Takich ciągów jest {n \choose 1}\cdot 5^{n-1}=n\cdot 5^{n-1}. Symbol Newtona odpowiada wybraniu jednego z n miejsc dla szóstki.
III: dokładnie dwa wyrazy ciągu są równe 6. Takich ciągów jest {n \choose 2}\cdot 5^{n-2}= \frac{n\cdot (n-1)}{2} \cdot 5^{n-2}. Tutaj symbol Newtona analogicznie.
Na koniec sumujemy te przypadki i odejmujemy od 6^n.

Losowanie ze zwracaniem ma głębszy sens, jeżeli po tym losowaniu ze zwracaniem też coś będziesz losował.
Góra
Mężczyzna Offline
PostNapisane: 11 kwi 2016, o 20:08 
Użytkownik

Posty: 47
Już jasne. Odnośnie losowania, to czy wybierając n elementów ze zbioru ze zwracaniem nadal bierzemy pod uwagę
Jan Kraszewski napisał(a):
Elementy w zbiorze zawsze są różne.

JK
czy po prostu możemy użyć w takim wypadku wzór na kombinację z powtórzeniami?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 14 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 N-wyrazowy ciąg bez trzech jedynek  acmilan  2
 utworzyć liczby czterocyfrowe z cyfr 0,1,2,3,4  monia255  1
 ile permutacji można utworzyć  Duke  1
 Ile roznych slow mozna utworzyc z liter :  Arleta19912  3
 ile samochów można zarejestrować w systemie  paulaa1992  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl