Na ile sposób można utworzyć ciąg.
-
- Użytkownik
- Posty: 44
- Rejestracja: 9 cze 2015, o 22:41
- Płeć: Mężczyzna
Na ile sposób można utworzyć ciąg.
Witam, mam problem z takim zadaniem - Na ile sposobów można utworzyć ciąg o 10 wyrazach ze zbioru \(\displaystyle{ \{1,2,...,123\}}\), tak aby dokładnie sześć jego elementów było parzystych?
Odpowiedź to: \(\displaystyle{ {10 \choose 6} \cdot 61 ^{6} \cdot 62 ^{4}}\)
\(\displaystyle{ 61 ^{6} \cdot 62 ^{4}}\) - ten fragment rozumiem, ale skoro tworzymy ciąg z powtórzeniami o długości \(\displaystyle{ 6}\) ze wszystkich liczb parzystych i ciąg z powtórzeniami o długości \(\displaystyle{ 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.
Odpowiedź to: \(\displaystyle{ {10 \choose 6} \cdot 61 ^{6} \cdot 62 ^{4}}\)
\(\displaystyle{ 61 ^{6} \cdot 62 ^{4}}\) - ten fragment rozumiem, ale skoro tworzymy ciąg z powtórzeniami o długości \(\displaystyle{ 6}\) ze wszystkich liczb parzystych i ciąg z powtórzeniami o długości \(\displaystyle{ 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.
Ostatnio zmieniony 8 kwie 2016, o 00:05 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych. Symbol mnożenia to \cdot.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych. Symbol mnożenia to \cdot.
- Waylays
- Użytkownik
- Posty: 59
- Rejestracja: 26 lis 2014, o 19:14
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 19 razy
- Pomógł: 8 razy
Na ile sposób można utworzyć ciąg.
Tak jak wspomniałeś, \(\displaystyle{ 61 ^{6}}\) odpowiada ilości wariacji z powtórzeniami \(\displaystyle{ 6}\)-elementowych ze zbioru \(\displaystyle{ 61}\)-elementowego. Analogicznie \(\displaystyle{ 62^{4}}\). Natomiast zauważ, że mnożąc tylko te dwie liczby dostaniesz odpowiedź dla ciągów, gdzie np. pierwsze \(\displaystyle{ 6}\) cyfr jest parzyste, a pozostałe nieparzyste. Jak sobie to zrobisz na papierze to zauważysz, że wychodzi własnie \(\displaystyle{ 61 ^{6}\cdot 62 ^{4}}\). A co z pozostałymi ciągami, gdzie na przykład na zmiane występują cyfry parzyste i nieparzyste? \(\displaystyle{ {10 \choose 6}}\) odpowiada wybraniu \(\displaystyle{ 6}\) miejsc dla liczb parzystych z \(\displaystyle{ 10}\) możliwych. Można równie dobrze wybrać \(\displaystyle{ 4}\) miejsca z dziesięciu dla nieparzystych, bo przecież
\(\displaystyle{ {n \choose k}={n \choose {n-k}}}\).
\(\displaystyle{ {n \choose k}={n \choose {n-k}}}\).
-
- Użytkownik
- Posty: 44
- Rejestracja: 9 cze 2015, o 22:41
- Płeć: Mężczyzna
Na ile sposób można utworzyć ciąg.
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 \(\displaystyle{ 10}\) elementów, które należą do zbioru \(\displaystyle{ \{1, 2, . . . , 123\}}\)?" odpowiedź wynosi \(\displaystyle{ {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?
-- 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 \(\displaystyle{ 10}\) elementów, które należą do zbioru \(\displaystyle{ \{1, 2, . . . , 123\}}\)?" odpowiedź wynosi \(\displaystyle{ {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?
Ostatnio zmieniony 8 kwie 2016, o 00:06 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Administrator
- Posty: 34125
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5192 razy
Na ile sposób można utworzyć ciąg.
Elementy w zbiorze zawsze są różne.WhiteRabbit7 pisze:skoro w treści zadania nie jest wspomniane o zbiorze zawierającym różne elementy?
JK
-
- Użytkownik
- Posty: 44
- Rejestracja: 9 cze 2015, o 22:41
- Płeć: Mężczyzna
Na ile sposób można utworzyć ciąg.
I wszystko jasne. To ostatnie pytanie na dzisiaj - "dla \(\displaystyle{ k \ge 3}\), ile jest ciągów \(\displaystyle{ k}\)-elementowych o wyrazach ze zbioru \(\displaystyle{ \left\{ {1,2,3,4,5,6}\right\}}\), gdzie co najmniej trzy z wyrazów ciągu są równe \(\displaystyle{ 6}\) ?"
Dlaczego odpowiedź \(\displaystyle{ {k \choose 3} \cdot 6 ^{k-3}}\) jest niepoprawna? Rozumuję w ten sposób, że na początku obliczam ilość możliwości umieszczenia \(\displaystyle{ 6}\) na \(\displaystyle{ k}\) pozycjach, zatem \(\displaystyle{ {k \choose 3}}\), a następnie na pozostałych rozmieszczam resztę liczb łącznie z \(\displaystyle{ 6}\), ponieważ liczba \(\displaystyle{ 6}\) może wystąpić ze względu na to, że \(\displaystyle{ k \ge 3}\).
Dlaczego odpowiedź \(\displaystyle{ {k \choose 3} \cdot 6 ^{k-3}}\) jest niepoprawna? Rozumuję w ten sposób, że na początku obliczam ilość możliwości umieszczenia \(\displaystyle{ 6}\) na \(\displaystyle{ k}\) pozycjach, zatem \(\displaystyle{ {k \choose 3}}\), a następnie na pozostałych rozmieszczam resztę liczb łącznie z \(\displaystyle{ 6}\), ponieważ liczba \(\displaystyle{ 6}\) może wystąpić ze względu na to, że \(\displaystyle{ k \ge 3}\).
Ostatnio zmieniony 8 kwie 2016, o 01:45 przez Jan Kraszewski, łącznie zmieniany 3 razy.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
-
- Użytkownik
- Posty: 144
- Rejestracja: 7 gru 2015, o 17:20
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 17 razy
- Pomógł: 16 razy
Na ile sposób można utworzyć ciąg.
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.
-
- Użytkownik
- Posty: 44
- Rejestracja: 9 cze 2015, o 22:41
- Płeć: Mężczyzna
- Waylays
- Użytkownik
- Posty: 59
- Rejestracja: 26 lis 2014, o 19:14
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 19 razy
- Pomógł: 8 razy
Na ile sposób można utworzyć ciąg.
Chodzi o to, żeby co najmniej \(\displaystyle{ 3}\) wyrazy twojego ciągu były równe \(\displaystyle{ 6}\), co gwarantujesz sobie przez symbol Newtona. Następnie liczysz liczbę wariacji z powtórzeniami \(\displaystyle{ k-3}\)-elementowych ze zbioru \(\displaystyle{ 6}\)-elementowego, co znaczy, że także \(\displaystyle{ 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ę \(\displaystyle{ 6}\), czy też nie. Według mnie do problemu należałoby podejść tradycyjnie, czyli zsumować wszystkie przypadki, gdzie szóstek będzie odpowiednio \(\displaystyle{ 3, 4, 5, ..., k \quad dla \quad k \ge 3}\). Jednakże mając na uwadze to, że już dla małego \(\displaystyle{ 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:WhiteRabbit7 pisze:Dlaczego odpowiedź \(\displaystyle{ {k \choose 3} \cdot 6 ^{k-3}}\) jest niepoprawna?
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 \(\displaystyle{ 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 \(\displaystyle{ k}\) i tyle.
-
- Użytkownik
- Posty: 44
- Rejestracja: 9 cze 2015, o 22:41
- Płeć: Mężczyzna
Na ile sposób można utworzyć ciąg.
Ale skoro robię wariację z powtórzeniami, to mam pewność, że zostaną wyliczone wszystkie przypadki, łącznie z tymi gdzie liczby \(\displaystyle{ 6}\) na tych \(\displaystyle{ 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.Waylays pisze:Chodzi o to, żeby co najmniej \(\displaystyle{ 3}\) wyrazy twojego ciągu były równe \(\displaystyle{ 6}\), co gwarantujesz sobie przez symbol Newtona. Następnie liczysz liczbę wariacji z powtórzeniami \(\displaystyle{ k-3}\)-elementowych ze zbioru \(\displaystyle{ 6}\)-elementowego, co znaczy, że także \(\displaystyle{ 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ę \(\displaystyle{ 6}\), czy też nie.WhiteRabbit7 pisze:Dlaczego odpowiedź \(\displaystyle{ {k \choose 3} \cdot 6 ^{k-3}}\) jest niepoprawna?
- Waylays
- Użytkownik
- Posty: 59
- Rejestracja: 26 lis 2014, o 19:14
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 19 razy
- Pomógł: 8 razy
Na ile sposób można utworzyć ciąg.
Okay, żeby uwidocznić błąd, który nam się wkradł, przypatrzymy się konkretnemu przypadkowi. Na przykładzie \(\displaystyle{ 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. \(\displaystyle{ 3}\) pierwsze miejsca, czyli mamy \(\displaystyle{ \left( 6, 6, 6, x\right)}\). Teraz uważasz, że na ostatnim możemy wstawić cokolwiek, także szóstkę. No to mamy wtedy \(\displaystyle{ \left( 6, 6, 6, 6\right)}\). Teraz chcemy wybrać ostatnie trzy miejsca, czyli \(\displaystyle{ \left( x, 6, 6, 6\right)}\). Jeżeli teraz postawimy szóstkę na początku, to okazuje się, że policzymy \(\displaystyle{ \left( 6, 6, 6, 6\right)}\) dwa razy. Ogółem dla \(\displaystyle{ k=4}\) policzymy w ten sposób \(\displaystyle{ 4}\) razy to samo ustawienie \(\displaystyle{ \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 \(\displaystyle{ 4}\) możliwości ulokowania \(\displaystyle{ x}\), gdzie \(\displaystyle{ x}\) mógłby być dowolną liczbą naturalną od \(\displaystyle{ 1}\) do \(\displaystyle{ 5}\) (razem \(\displaystyle{ 4\cdot 5=20}\)) i jeszcze dodajemy \(\displaystyle{ 1}\), dla czterech szóstek (zamiast liczyć \(\displaystyle{ 4}\) razy takie ustawienie, liczymy raz).
I: \(\displaystyle{ {4 \choose 3}\cdot 5^{4-3}=4\cdot5=20}\)
II: \(\displaystyle{ {4 \choose 4}\cdot 5^{4-4}=1\cdot 1=1}\)
\(\displaystyle{ 20+1=21}\)
Wynik jak najbardziej prawidłowy, żeby się upewnić sprawdziłem w programie i było okay.
Czyli w tym wypadku po prostu zachodziłyby \(\displaystyle{ 4}\) możliwości ulokowania \(\displaystyle{ x}\), gdzie \(\displaystyle{ x}\) mógłby być dowolną liczbą naturalną od \(\displaystyle{ 1}\) do \(\displaystyle{ 5}\) (razem \(\displaystyle{ 4\cdot 5=20}\)) i jeszcze dodajemy \(\displaystyle{ 1}\), dla czterech szóstek (zamiast liczyć \(\displaystyle{ 4}\) razy takie ustawienie, liczymy raz).
I: \(\displaystyle{ {4 \choose 3}\cdot 5^{4-3}=4\cdot5=20}\)
II: \(\displaystyle{ {4 \choose 4}\cdot 5^{4-4}=1\cdot 1=1}\)
\(\displaystyle{ 20+1=21}\)
Wynik jak najbardziej prawidłowy, żeby się upewnić sprawdziłem w programie i było okay.
-
- Użytkownik
- Posty: 44
- Rejestracja: 9 cze 2015, o 22:41
- Płeć: Mężczyzna
Na ile sposób można utworzyć ciąg.
Oto rozwiązanie zadania:
\(\displaystyle{ 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:
\(\displaystyle{ 6 ^{n}}\) - obliczamy wszystkie możliwe wariacje z powtórzeniami, a następnie będziemy odejmować od nich nie interesujące nas ciągi
\(\displaystyle{ 5 ^{n}}\) - po odjęciu tej wariacji otrzymamy wszystkie możliwe ciągi, które zawierają na przykład liczbę \(\displaystyle{ 6}\)
\(\displaystyle{ 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.
\(\displaystyle{ {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?
\(\displaystyle{ 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:
\(\displaystyle{ 6 ^{n}}\) - obliczamy wszystkie możliwe wariacje z powtórzeniami, a następnie będziemy odejmować od nich nie interesujące nas ciągi
\(\displaystyle{ 5 ^{n}}\) - po odjęciu tej wariacji otrzymamy wszystkie możliwe ciągi, które zawierają na przykład liczbę \(\displaystyle{ 6}\)
\(\displaystyle{ 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.
\(\displaystyle{ {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?
- Waylays
- Użytkownik
- Posty: 59
- Rejestracja: 26 lis 2014, o 19:14
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 19 razy
- Pomógł: 8 razy
Na ile sposób można utworzyć ciąg.
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 \(\displaystyle{ 6}\). Takich ciągów jest \(\displaystyle{ 5^n}\)
II: dokładnie jeden wyraz ciągu jest równy \(\displaystyle{ 6}\). Takich ciągów jest \(\displaystyle{ {n \choose 1}\cdot 5^{n-1}=n\cdot 5^{n-1}}\). Symbol Newtona odpowiada wybraniu jednego z \(\displaystyle{ n}\) miejsc dla szóstki.
III: dokładnie dwa wyrazy ciągu są równe \(\displaystyle{ 6}\). Takich ciągów jest \(\displaystyle{ {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 \(\displaystyle{ 6^n}\).
Losowanie ze zwracaniem ma głębszy sens, jeżeli po tym losowaniu ze zwracaniem też coś będziesz losował.
I: żaden z wyrazów ciągu nie jest równy \(\displaystyle{ 6}\). Takich ciągów jest \(\displaystyle{ 5^n}\)
II: dokładnie jeden wyraz ciągu jest równy \(\displaystyle{ 6}\). Takich ciągów jest \(\displaystyle{ {n \choose 1}\cdot 5^{n-1}=n\cdot 5^{n-1}}\). Symbol Newtona odpowiada wybraniu jednego z \(\displaystyle{ n}\) miejsc dla szóstki.
III: dokładnie dwa wyrazy ciągu są równe \(\displaystyle{ 6}\). Takich ciągów jest \(\displaystyle{ {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 \(\displaystyle{ 6^n}\).
Losowanie ze zwracaniem ma głębszy sens, jeżeli po tym losowaniu ze zwracaniem też coś będziesz losował.
-
- Użytkownik
- Posty: 44
- Rejestracja: 9 cze 2015, o 22:41
- Płeć: Mężczyzna
Na ile sposób można utworzyć ciąg.
Już jasne. Odnośnie losowania, to czy wybierając n elementów ze zbioru ze zwracaniem nadal bierzemy pod uwagę
czy po prostu możemy użyć w takim wypadku wzór na kombinację z powtórzeniami?Jan Kraszewski pisze:Elementy w zbiorze zawsze są różne.
JK