Na ile sposób można utworzyć ciąg.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
WhiteRabbit7
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 9 cze 2015, o 22:41
Płeć: Mężczyzna

Na ile sposób można utworzyć ciąg.

Post autor: WhiteRabbit7 »

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.
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.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Na ile sposób można utworzyć ciąg.

Post autor: arek1357 »

Bo wybierasz te miejsca z dziesięciu na których będą stały wyrazy parzyste.
Awatar użytkownika
Waylays
Użytkownik
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.

Post autor: Waylays »

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}}}\).
WhiteRabbit7
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 9 cze 2015, o 22:41
Płeć: Mężczyzna

Na ile sposób można utworzyć ciąg.

Post autor: WhiteRabbit7 »

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?
Ostatnio zmieniony 8 kwie 2016, o 00:06 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Jan Kraszewski
Administrator
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.

Post autor: Jan Kraszewski »

WhiteRabbit7 pisze:skoro w treści zadania nie jest wspomniane o zbiorze zawierającym różne elementy?
Elementy w zbiorze zawsze są różne.

JK
WhiteRabbit7
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 9 cze 2015, o 22:41
Płeć: Mężczyzna

Na ile sposób można utworzyć ciąg.

Post autor: WhiteRabbit7 »

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}\).
Ostatnio zmieniony 8 kwie 2016, o 01:45 przez Jan Kraszewski, łącznie zmieniany 3 razy.
Powód: Symbol mnożenia to \cdot.
Janpostal
Użytkownik
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.

Post autor: Janpostal »

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.
WhiteRabbit7
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 9 cze 2015, o 22:41
Płeć: Mężczyzna

Na ile sposób można utworzyć ciąg.

Post autor: WhiteRabbit7 »

Treść zadania poprawiona, przepraszam za błąd.
Awatar użytkownika
Waylays
Użytkownik
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.

Post autor: Waylays »

WhiteRabbit7 pisze:Dlaczego odpowiedź \(\displaystyle{ {k \choose 3} \cdot 6 ^{k-3}}\) jest niepoprawna?
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:
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.
WhiteRabbit7
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 9 cze 2015, o 22:41
Płeć: Mężczyzna

Na ile sposób można utworzyć ciąg.

Post autor: WhiteRabbit7 »

Waylays pisze:
WhiteRabbit7 pisze:Dlaczego odpowiedź \(\displaystyle{ {k \choose 3} \cdot 6 ^{k-3}}\) jest niepoprawna?
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.
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.
Awatar użytkownika
Waylays
Użytkownik
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.

Post autor: Waylays »

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.
WhiteRabbit7
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 9 cze 2015, o 22:41
Płeć: Mężczyzna

Na ile sposób można utworzyć ciąg.

Post autor: WhiteRabbit7 »

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?
Awatar użytkownika
Waylays
Użytkownik
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.

Post autor: Waylays »

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ł.
WhiteRabbit7
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 9 cze 2015, o 22:41
Płeć: Mężczyzna

Na ile sposób można utworzyć ciąg.

Post autor: WhiteRabbit7 »

Już jasne. Odnośnie losowania, to czy wybierając n elementów ze zbioru ze zwracaniem nadal bierzemy pod uwagę
Jan Kraszewski pisze: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?
ODPOWIEDZ